Secret victory conditions
Heh, just earlier I was thinking "Sheesh people, the game isn't even beta for 6-8 months. Give them a shot at what they want to create first before spewing ideas."
And yet, here I am spewing.
One of my favorite PBM games, Alamaze, had secret victory conditions. Every kingdom in the game has a random (though tailored to the kingdom somewhat) secret victory condition in addition to the normal ones, though secret was the typical way to win and a "normal" win was considered a total ass kicking.
I think something like that might be cool in a 4X game. Rather than the same old goals, you'd have winning goals slightly shifted each game. In Alamaze, you could "research" an opponents secret victory condition, so if you got suspicious about someone say, spreading into a million villages, but staying away from powerful towns and cities, you might research and see if they had some sort of secret "ubiquitous presence" type victory condition.
Brad has already talked about multiple paths to victory in Elemental and that military is only one means. I think making part of that victory condition hidden (but researchable) might provide a real boost to the tension and give you a reason to never quite ignore some middling power kingdom that's behaving a little oddly. It'd also be an aspect of "spying", if the game has that, or the creation of a unit or hero ability or spell or some such to gain that special info.