On two games now, I've explored the whole map and been unable to find the last sovereign. I'm playing with max number of enemies.
I believe, but can't confirm, that they might be stuck on an island somewhere off the edge of the main continent. I haven't even seen borders for their city, however, so I really don't know.
I suppose I could attach a screenshot of a fully explored map, but I'm not sure how helpful that would be.