1. Diminishment - Game starts with palyers immensely powerful, but they tend to diminish in power over time. This could be accomplished nicely with finite resources, or dwindling resource rates, the permanent expenditure of power, etc.
Elemental will have random events, right? I figure, a great way to do diminishment would be to give you a nice, big empire and crank the frequency of bad random events way up through the roof. Maybe they start extremely common, like with at least one guaranteed per empire per turn, and taper off somewhat as the various empires fall to shit from all the plagues, riots, earthquakes, floods, hurricanes, "accidents" caused by careless mages, barbarian/demonic invasions, and whatever other nasty stuff you can think of. It would somewhat solve the "hurr screwed by the RNG" problem I normally have with bad random events, since everyone's getting hammered by them.
This could be tied into the survival idea by making one empire immune to these events.
Call me lame, but I actually wouldn't mind a capture the flag game type... Like where there would be X magic nodes and if you capture them you can channel their energy to build a new world or something cheesy like that. (I'm tired >.<)
This is always a very good thing to include, because if you're strong and advanced enough to capture enough flags, you're pretty much always the goliath mentioned in the survival idea. So, these victory conditions are a good way to circumvent the whole "okay, you've won, now for the tedious process of actually WINNING" probelm 4x games tend to have.
Stardock somewhat bungled this idea in GC2 with the ascension victory. The problem was that it took too long to gather enough ascaneion points unless you settled a whole bunch of crystals, which made everyone hate you and attack you, which was a problem because ascension starbases are very easily griefed... yet despite these problems, it was still a viable win condition for people who didn't want to destroy everyone or cover most of the map in thier influence.
The current incarnation of Fall from Heaven's tower of mastery victory is a great example of this win condition. For those unfamiliar, there are 5 buildings which are dead easy for a mature empire to build, if you build them you win. In order to be able to build them, you need to acquire at least one source of each mana type (except for ice and metamagic which are wierd oddballs.) It requires a good combo of muscle, emprie size, tech speed and building capability to get these sources. If you have it, you're strong enough to win by domination, but you don't have to go through the trouble of actually doing it.