I personally would like it if defeating an elemental lord gave you the ability to train (or spawn like the recruitable monsters) shrills and elementals of that type in the city where you set up the trophy.
Something like:
City Level Bonus Creature
1 Shrill
2 The snake-like elementals for fire (Ignys) and earth (ophidians), whatever is equivalent for water, air, and the last one
3 Elemental
4 Shrill Lord
5 Elemental Lord
Speaking of which, who is the fifth elemental lord and what is his element? Abeix for Earth, somebody with a T (Toranth? Torath?) for Air, Delin for Fire (I think, though his description indicates he might not be), Vetrar for water, and ??? (is it Morian?) for ?Life and Death.
Also, units: we have shrills and elementals for the classical magic elements of Earth, Air, Fire, and Water, and we have the Ignys and Ophidian that are minor elemental-like creatures for Fire and Earth, but I can't think of anything but demons that might be elementals for the fifth element, nor am I aware of equivalents to Ignys and Ophidians for Water and Air. Crag Spawn are essentially equivalent to Ophidians, but both seem associated with Earth to me, and I can't think of other monsters that could fit in a similar place for Air and Water.
Taking Deorcynsse should at least give you a unique city, not one that just ends up looking the same as any other as soon as you get the city to go up a level. Making it high level (and especially giving it unique improvements, and/or benefits for holding it) would go a long way in that direction.
I would also support having the wildlands that give fertile land after being cleared produce less of it but concentrate the bonus into one really great site for a city (similar to how I think the Ruins of the Imperium is supposed to work), and having certain wildlands (like the Lombard Desert, and maybe the Pits of Namtur) not spawn fertile tiles upon being cleared but rather have lots of resource tiles or very good resource tiles that you can claim with outposts after clearing the wildland.