The problem with WoW's story I always felt was this.
In FFXI when you killed the AA's or other mission bosses that was it. That was the end of that story, you didn't farm missions for loot each week or anything. Granted you could go back and help your friends, but that's besides the point.
In WoW you have these giant enemies of the world like C'Thun, Yogg, Nef, Rag, even Arthas. Once you've killed them you might get a special treat like an in game scene like Illidan or Deathbringer, but more times then naught it's just a "loot the body and keep moving" type deal. And you'll be farming these guys over and over again for w/e loot you deem you need.
WoW has some decent story and lore to the dungeons you enter, but some of the bosses are never made reference to before you face them. I get Marrowgar is the guard of the citadel...but how did he come about? Does he have a story behind him? What about Lady Deathwhisper? What about the Blood Princes? I know a little about them but WoTLK never really tells us too much about their whole deal.
I am loving going through Northrend though as alliance now. The quests and stories behind them are really interesting. I feel like I missed a lot leveling as horde through WoTLK first.