WoW does not even have a decent flowing sotryline from beginning to end. Its all a bunch of small ones that make up a handfull of quests. More like a "pulp fiction" than an full story.

Guild Wars: Nightfall, Prophecies, and Eyes of The North have great storylines. Prophecies flows very well into Eyes.

The most immersive story I have encountered would be Lord of The Rings. You feel like your part of the actual trilogy while not actual being involved the the stories. You get involved with stories that fill in the background of the trilogy and you also intersect many key points that would relate to the trilogy.

Another thing that makes LoTR the most immersive stroyline is the fact that the PvP is 100% seperate from the actual story and quests. It still has PvP, but you would have to reach a high level and travel to a region that is seperate from the real lore.

The enviroment, the NPCs, and the graphics are fully involved with the immersion into the game.