I have same thing happening in my game
Medium map, 4 opponents - other three all have settlements but Procipinee standing around with initial units 2 steps away from basic 3/3/0 settlable tile and 3 moves from a large amount of choice tiles

Had same with both custom and vanilla factions. It appears that they just never bothered to settle, and instead their AI is completely non-functional, only in specific games.

If this is the case, there should be an additional caviet: If the AI has not settled by turn 10, total priority is for the AI to find the closest location and settle.

Is it possible that in some of the games the AI could have settled but monsters or ruffians destroyed their settlement but the sovereign and their army was still alive?

I can confirm that a Sovereign without cities can always settle a "first" city.

I can also confirm that I encountered a Vanilla Faction (Gilden) sitting in the corner of the map without any settlable spots due to the Win-the-game-quest-location blocking all tiles. I do not know why Gilden didn't move away from there..

I don't know what part, if any, difficulty levels play in this, my observations are all from Normal/Challenging modes. I only play with custom AIs, and watched the beginnings of a lot games with the map revealed during beta. They always eventually settle, but I have seen them take several turns to finally pick a spot. Sometimes they will just sit for a turn or two, I guess chugging down a last shot of courage or something. Other times they'll beeline a goodie hut before settling, while ignoring others. This can happen even if you move them to an optimal tile before their first turn.

Same as you

I think this must be what happened to me in a ridiculous game the other day in version 1.0. After 250 turns Altar had not been encountered by any AIs and had not been declared defeated either. I couldn't find their sovereign anywhere though. I've never seen it happen before or since.

judging by the save game the threadstarter provided, i think in this case the proximity to the wildland may have been the problem. i don't know how AI evaluates settling spots, but there may be some function that tells them to not settle too close to a wildland. maybe also with a condition -if faction power is below a certain score, don't settle in dangerous zones [next to wildland, within X tiles of a strong/dangerous lair etc].

i've noticed similar behavior with AI before. sometimes there are nice spots guarded by strong or dangerous lairs. AI won't settle them while they can't handle the guardians. if you remove the lair, they'll happily settle the spot within a few turns. don't know if all AI act like that - could also be related to AI modifiers/personalities (and probably also AI difficulty - on higher settings they tend to expand more aggressively in my experience)