I am fairly certain its been more than considered.  Just it isn't a very major feature to implement, and I can't imagine it would need much in the way of testing (in comparison to other features)

some quest events, if nothing else, can count as random events.   Surely we'll see something similar to Galactic Civilization's events as well.

Yes, there will be nothing more exciting than hearing "Hordes of ice trolls have been spotted in the northern tundras!" and watching them lay waste to your enemies as you snatch up the newly freed land 

Dominions 3 had an awesome event where a party of high level, well equipped adventurers decided to overthrow the evil tyrant (that would be you) and seize control of one of your provinces. You typically end up raising a massive army of redshirts to overwhelm the elite adventurers in a hilarious reversal of typical RPG play - something like that would be perfect in Elemental. The adventurers could spawn near a city (not the capital) and try to capture it, or just settle a new city within your territory, then make a nuisance of themselves by attacking any nearby units and refusing diplomacy. In fact, if it can be weighted to strike more often against players that are ahead (in score and/or number of cities), it'd be a great anti-steamroller mechanic.

'Course this isn't all that different from what the current NPCs do, but rather than a wandering group of adventures picking on an undefended city, these would be significantly more powerful NPCs spawned right next to a target city that they automatically attempt to capture even if it's defended, and if possible they'd prefer the most powerful/largest empire as their target.