Another issue I have seen is Civs running Theocracy but having no State Religion!!
I don't think the AI would ever choose to do this under normal conditions. I can only think of two times this might happen: either the AI is just about to adopt a state religion within the next few turns; or their state religion was eliminated from their civilization (maybe the cities were captured or something).
I can't see anything in the civic evaluation function which would give any kind of value to Theocracy without a state religion (or intention to have a state religion). If you have an example of the AI doing this which doesn't match the possible cases I described, then it might be a bug, and I'd like to see a save game to reproduce it.
--
As for the founding of early religions, it's important to keep in mind that the AI's tech choices are quite situational, and have a good chunk of randomness too. So I'm not surprised that it's sometimes possible to beat the AI to all of the early religions. And even if the tech choices weren't situational, I can imagine cases whether they AI is trying to get a religion, but failing because it's just a couple of turns behind you in research. It might be going after every religion that you go for, but just barely missing out every time. - So for those reasons, one shouldn't put much weight in one-off events in isolated games.
The big questions are these: does this happen often? And when you do beat the AI to all the early religions, is it worth it? If going after all the religions end up making you worse off by putting you behind in other techs, then it probably isn't something the AI should be too concerned about. I've often heard humans giving the following advise to each other in other parts of these forums:
don't bother going for the early religions. It's better to just let the AI get them and then capture the holy city by force if you really want it. I think it's probably good if that kind of strategy isn't always the best option.
In any case, I'm interested to hear of other examples and opinions on this. Isolated cases doesn't really mean much to me, but when a bunch of isolated cases start gathering together, they cease being isolated.