I'm not aware of any MMOs out there that function the way you describe. Existing games typically focus on one of two ideas: the pre-written, detailed, heavily scripted story, or the socially driven, emergent story.
Pre-written story lines will occasionally offer branching points for the story to evolve but in the end all outcomes and paths are predetermined. Most MMOs also safeguard players from having their stories affected by other players not partaking in them. Some games introduce variation where stories are based off of a template with events, locations, rewards, etc randomly selected from a pool, however the templates, variables, and selection criteria are ultimately written by hand.
What you are after sounds more like an evolution of the random story, but where the selections are made based on the state of the game world rather than simply randomly. Unfortunately I know of no existing MMO that does this.
As a social platform MMO's have a rather rich and dynamic environment of player ambitions and interactions and so here is the alternative route of story telling - the socially emergent one. Games that employ this directly or indirectly offer players goals and methods to achieve them, while encouraging conflict of one form or another. The aforementioned Eve Online is a great example of this. Here, stories often become very personal, not only contributing to the virtual identity of an individual player but also to the groups the player is a member of since such stories are usually played out through cooperation, potentially with thousands of players.
<insert="shameless Eve Online plug">
http://www.youtube.com/watch?v=08hmqyejCYU</insert>
Neither of the two story telling methods present in current MMO's fit your requirements. What you are looking for is something in between. If
I were to design such a system social conflicts would affect the parameters of the game world, and the effects of which would be used to select criteria for the generation of AI controlled stories.
TL;DR
You are in new territory. There is no MMO out there that does story telling the way you are describing (perhaps this is the point?). If you are looking for one that just offers unique and dynamic experiences to its players regardless of the methods utilized, I recommend Eve Online.
Side Note: Eve Online uses both methods, although separately. The pre-generated story content is quite lacking compared to other MMO's. The real story is found in the player corps and alliances. If you join the game find some other people and try to accomplish something tangible.