I've been playing Persia --for last 72 hrs+
ran into same catch 22 and wrote to the civ guys.
Building a forbidden palace in a lawless frontier is next to impossible.
In the end i had to wait until modern times to be able to finally stick one in (losing countless turns of effciency). Now my empire is so vast that i really need 3 palaces as i still have 1/3 of the world still to conquer.
I would think the need for palaces should be tied to size of world
and then number of cities could be a sub requirement.
With the latest patch...my expenses have increased 1300 as a commie!!