I used to think that it was patently impossible to tell a changing story within an MMO, or more specifically, and MMORPG. I thought that world needed to remain static on account of the fact that you have thousands of people all playing the same game, and at different points. If Joe the farmer wants you to kill 10 boars so he can cook dinner that night, the boars can't very well stay dead. They need to respawn so a thousand other people can also kill them for Joe the farmer's dinner.
This seems like a nuance, an effect on the story you can just hand-wave away as a necessary game mechanic. But it becomes more pronounced as the game brings you to do more prominent and amazing things. The tons of unnamed thieves are fine to keep bringing back, but what about when the game asks you to kill their leader? 'Bandit Bob' actually has a name. He has a purpose. He's not some nameless recruit on his band of thieves. He IS the band of thieves. So you fight your way in, defeat Bandit Bob in potentially dishonorable combat, and inform the local townspeople that they are safe once again! Huzzah! As you leave the town for your next adventure, you notice Bandit Bob has respawned.
Bandit Bob can never die, because a thousand other people have to kill him too. Kinda breaks the immersion of the story, doesn't it? You just finished saving this town from the bandit menace and yet they still exist. What do you do about that little hiccup in the story there?
I haven't really played any other MMORPG's, but I'm nothing if not a World of WarCraft fan. Blizzard took a look at this problem and created a storytelling technique to deal with it. They call it "phasing". Under the phasing system, each character sees as far as they've progressed in any particular story. If your character has never been to Little Town By The Bay, you'll see Bandit Bob and his no good cronies harassing the citizenry. So you ready your trusty Melt Some Faces spell and lay waste to the bandit horde. Bandit Bob falls before your incredible might!
And he stays dead. By doing this, you've just entered the next part of the story and a new "phase". For your character, the citizens of Little Town By The Bay will forevermore be safe. The thousands of other characters who have never been here will still see a town being attack by thieves.
This phasing technique offers a very interesting capacity to tell a changing story in an unchangeable world. Any given character's actions will now have a lasting impact that they can see. Did you just help your army take a forward position from the enemy? They'll hold it. Did you just assist in blowing up an enemy camp using enough explosives to terraform a mountain? There will always be a huge crater where solid ground once stood.
Now, this is nothing new for a single-player experience. The story progresses and things change, because the only person the game world has to worry about is you. Something a bit more interesting, doing even more to change the unchangeable, is how the community can actually help shape an evolving game world and the story it tells.
For its latest expansion, World of WarCraft re-did almost the entirety of their old content. Things that have normally been around since the game was first released are now gone, replaced with new material to reflect developments within the story. Among these are some changes that reflect the community.
As prime example is in the city of Orgrimmar, capital to one of the game's factions. When the game was released, the local inn contained a hapless cow-man (Tauren) named "Gamon". NPC members of your faction are friendly to you, they will not attack you and you cannot attack them. But poor Gamon, due to a series of necessary game mechanics, was required to be neutral. Neutral NPCs will not attack you until you attack them.
So, here we have this neutral, low level NPC that's supposed to be part of the player's faction. This obviously wasn't going to end well. Just about any player that walked in to the city would find Gamon and kick him around for fun. It became part of everyday life in that city. Some players said they enjoyed it, it made Orgrimmar feel like a rough place to live.
Now, flash forward to this newest expansion, where everything has been remade. Gamon still spends his time in the local inn. Except now he carries a battle axe, he's maximum level, and he's elite (meaning he's much tougher than a normal NPC of that level). The community made a sport out of beating up this poor NPC for years, so Blizzard saw fit to evolve the story around them. All those beatings tempered him into a tough fighter. He's still neutral, except now he'll kick around any players that dare still attack him.
An even bigger example is the town of Southshore. Years ago the player base used to involve themselves in titanic player vs. player battles between two little towns in the middle of nowhere, called "Southshore" and "Tarren Mill". Each was controlled by a different faction. Little fights in these areas would quickly escalate into huge battles as people called in their friends to assist. It became the stuff of legend.
With the advent of the new expansion, this too was acted upon. Control of Southshore changed hands and it's now manned by NPCs of the opposite faction. The player base started the war over these two towns and the game eventually changed to accommodate that. It declared a victor, and to the victor went the spoils.
So, now we have the players influencing the story of the game beyond the scope of what they play. Blizzard decided that Bandit Bob would have to die as part of the story, but the players decided that two innocuous towns would be the focal point for the war they were supposed to be fighting. A very interesting notion for a game that seems so unchangeable, and for any game in general. How often does the player tell the story, instead of the game?
(Disclaimer: Gamon, Southshore, and Tarren Mill all exist in the game. Farmer Joe and Bandit Bob are both fictitious entities that I made up just as throwaway examples.)