A different train of thought got me to thinking about Space Station 13, but then I connected that with this conversation and figured I should... just point out Space Station 13, I guess. It really is one of the most prime examples of... I want to say "emergent storytelling" in gaming, but that phrase makes me feel like punching myself in the mouth. "Story as a goal" might be a bit better.
SS13 is one of the few games I can think of where telling the story is the player's true main objective. There are other objectives to complete, of course, but all of these largely come secondary to the primary focus of storytelling*. Completing your objectives at the cost of narrative will usually get you banned, in fact.
Those in-game objectives, though, are one of the big reasons why I think SS13 works as a true multiplayer role-playing game, as opposed to a lot of games that try for it but sort of grind down to a bunch of avatars describing actions to each other. Conflict is pretty much the main source of interesting things happening in a story, and conflict is created by people or entities having, er, conflicting goals. In most video games this is present, although the conflict is pretty basic: You are trying to accomplish a goal, and the other entities in the game are either trying to stop you, or do something which would prevent you from accomplishing your goal (e.g. kill you). SS13 does pretty much the same thing in a less direct way: You're usually not being thwarted directly as such (unless you're a traitor or doing something patently illegal), but in almost every round you can be sure that someone, somewhere is going to make things tricky for you.
It's a rare, but not necessarily unique system in video games. The Ship is based around the same concept, albeit in a much more simplified manner. Most multiplayer games will put players in direct conflict, but then the stories become about as simple as the motivators that drive them: "And then I shot the other guy!" Some games that aspire to be true role-playing games, like Neverwinter Nights, do a lot right but either don't provide the players with such a diverse set of operating parameters or simply don't provide as many things that can otherwise go wrong for the game to be interesting. SS13 not only puts the burden of insanity on the players, it crams further insanity into every overly detailed game feature.
Computers generally do a poor job of imitating the creativity of humans but if you truly want to "create" stories out of the interaction of the player and the in-game entities, then creating entities with much more various goals and interactions is a good start. At the very least, you'll get stories out of it that are more complex than "That NPC tried to kill me, so I shot him."
* Before you think I'm being high-falutin' about this, keep in mind that the "stories" in Space Station 13 usually involve people murdering each other with zambonies, shitting their own asses off and bleeding to death in access vents, and trying to make ground beef out of dead xenomorphs.