I have an idea for something similar to quests, prophecies. They're basically quests, but with a certain structure.
A Prophecy can be triggered at the beginning of a game, or after specific events, like conquering a town, defeating another player, discovering a monster lair, or similar things.
Like any prophecy, it will foretell the coming of a hero, or of a great evil, or something similar. It can give a precise date, a vague date, or it can specify an event after witch the prophecy will take place. Unlike a quest regular quest, the player does have ample time to prepare, or to try and interpret what it meant if it was to vague. Perhaps some for of researcher can be assigned to make sense of it, by spending some money.
Another difference from regular quest would be that a prophecy implicates a larger portion of the game. For example, the same prophecy can foretell the doom of a player, and the success of another. Meaning that when it begins, one player suffers a loss in some area, and another one revives an advantage, depending on what role they play in the prophecy.
When the time of prophecy finally comes, the player could help fulfil it, if it is beneficial for him, or try to stop it from happening. Each outcome would have an effect, fulfilling a beneficial prophecy would grant that player the reward promised. Failing to fulfil it could bring disadvantages, or maybe delay it.
Now for the fun part. A player could have the possibility of melding in the prophecy of another player. Let's say the prophecy player A receives calls for a hero to defeat a great beast and consume it's power to become a great champions. If player B kills that hero before he kills the beast, he would have stopped the prophecy. This would not earn him a reward directly, but it may bring the wrath of the gods upon the player A, and ensure he looses what was promised to be a great and powerful champion.
I'll give an example of what I am referring to. I'm using Master of Magic as a template.
Prophecy text and commentary notes:
"Beware great king, for when the savages of the wilds besiege your city(first city is attacked by neutral raiders), and the power that feeds your empire is snuffed out(mana shortage, all nodes stop producing power), a great evil(neutral and very powerful enemy, like a dragon) will arise in the south(general location of said evil). It shall descend upon your kingdom and wreak havoc. Powerless you will be to stop it, and great suffering will come. (dragon doing that it's best at)
But fear not my lord, for one shall arise to stop the evil. A child born from the shadow of stars(hint to the name of the hero, Darkstar) will come to you and pledge his loyalty. Guard him well, for when the time is right, he shall send the evil ravaging your empire back into the darkest depths from which it spawned.(doing what a hero does best).
(now comes the reward part)And when the evil is vanquished, the land shall be full of life, and for five seasons your harvest shall be bountiful and the envy of all other kingdoms.(for certain duration of time, food production sky-rockets). But be warned my king, should you fail, the evil shall have it's drink of your kingdom, and one day it shall return for your life.(in case of failing to kill the dragon, it will run amok, leave, and return after a few years to do it again)"
Prior to time of prophecy:
Hero Darkstar offers to work for the player. If he is accepted the prophecy can be fulfilled, if not, it is still can be, but to a lesser extent. They player could be able to kill the dragon without the aforementioned hero, but doing so will negate the harvest bonus.
Time of prophecy:
The dragon appears and starts to attack player controlled villages. The player can then send Darkstar to deal with the dragon. If he succeeds, the prophecy is over, good ending. If he fails, the dragon lingers for a few more turns doing bad things, then he leaves and returns after a few years. At that point there won't be a hero of prophecy any more, so the player would have to deal with the beast himself.
This was a small scale example. Like I said, a prophecy could implicate other players, and if the children of the sovereign are controllable units like he is at the beginning of the game, they could be part of a prophecy. The complexity of prophecies would be largely determined by the skill and dedication of whoever writes/codes it. At the high point we could end up with a retelling of Baldur's Gate in Elemental. And the rewards for prophecies would not be things that you can get from normal quests. For example, one of your heroes could become a demigod, an island filled with riches could rise out of the sea, a comet could strike your enemy, and other things that could effect the game on a large scale.
Because of this, prophecies could be optional, as in they could be toggled on or off at the creation of a game. And in the game, they would not come around very often, but each player should experience one every few hundred/thousand years.
I hope I managed to explain my idea well enough for it to be understood.
PS: A Time Travel spell would still be awesome.