Maybe a new specialist building (the ones that have an upkeep) would allow buildings to go above their max level. Call it something like the Palace or Parliament or City Ordinance Office or somesuch
2 building levels per level of parliament; raise building level limit by 1 for every X levels of Parliament(X=4 would allow level 25 buildings, X=5 would allow level 24, X=6 23, etc.)
so a level 4 parliament would allow you to build a total of 8 levels on buildings in your city above 20, but they would still be stuck by a cap of 21-22 or so. a level 20 parliament would allow 40 levels above 20, but again be hit by a cap at 22-25 (depending how many that'd be best to balance on).
The building itself would need quite high maintenance, be limited to the capital and would need to be exempt from it's own bonus.
It's simple enough that new players can grasp the concept easily, and promotes decision making in choosing which buildings get the extra levels as they become available.