1) Upgradable outposts.  Each level of outpost increases the strength of army needed to raze them, or the time needed to raze in an outpost's ZOC (unsure which is better)  

You ever notice how armies have Weak/Medium/Strong/Deadly/Epic?  Weak and Medium armies shouldn't be able to raze armies or capture cities without taking some time to do so, and stronger cities should be able to hold out much longer.

2) Siege engines would be required to capture walled cities.  Unwalled cities would be different.  Siege engines will also increase the sieging ability of an army for razing purposes.  I've also like to see magical catapults similar to the Maelstrom Engines in Kohan.  Catapults would also be able to do ranged attacks (mechanics similar to pillar of flame) so setting up catapults in your cities would be a good idea for defense.  (Maybe add a building that does this)

Earth Archmage might get a Wall Breaking spell that destroys walls for 100 mana, other magic spheres could get something like Rot Wood.

I think this would create a push towards bigger armies, which would push the AI into the "sharper spear" (which is where I think the AI work needs the most work- why does AI tend to stink at this?)