Probably the most famous unresolved story line in the history of WoW was that of The Missing Diplomat, which for years was an iconic Alliance quest in pursuit of the missing Stormwind king. You ended up in Dustwallow Marsh with Jaina Proudmoore's thanks for having tracked down one of the conspirators, and then ... silence. Until Wrath of the Lich King, players wondered what on earth had happened to King Wrynn.
Blizzard seems to be wrapping up a few stories that had been eluding players for a while (most recently, where Maeiv Shadowsong went after the battle with Illidan), but others remain. I have two personal favorites: The quest that Chromie gives you in Dragonblight that strongly hints at something weird going on with Nozdormu (admittedly, Thrall: Twilight of the Aspects sort of addresses this), and a question cryptically answered by Chris Metzen and Alex Afrasiabi in the first round of Ask CDev concerning the ultimate fate of Frostmourne. Is there any mouse-like storyline or quest thread you'd still like to see finished in game?