Speaking from the point of view of a scenario designer, it's quite easy to mistakenly deploy cities without a palace. Essentially, what happens is that the first city deployed for any given nation will, naturally, have a palace. But decisions down the line may cause one to remove that city in favor of a better position (perhaps more accurate, or better strategic placement). Anyhow, once the city is removed then the palace is gone... and it's not automatically replaced (unlike in the game, where there is a setting that's normally toggle on to replace palaces if they are captured).
Ultimately, I think Corbeau is right: the absence of a palace (and of a capital) is pretty catastrophic. Morbid curiosity leads me to want to see just how bad it gets with other governments (which one would be the worst?).