I think burning crusade did the best job personally.
In vanilla the story felt like it was all just so random... All these zones, each with their own little problems done in a self-contained way with no real effect on anything beyond that zone. The raids were all completely unrelated to each other and full of villains we'd never seen or heard of before. Etc.
In TBC however, we got to goto outland and fight the "bad guys" from warcraft 3. We fought kael'thas, vashj, and ultimately illidan. I wouldn't say it's WOW story was anything all that profound or amazing, but it was a continuation of the story that began in warcraft 3. Ilidan took over the black citadel in outland, locked up Magtheridon when he took his place as ruler, and just camped out with kael'thas and vashj all that time.
It was great. You had naga and blood elves all over the place doing their own little things all for the main unifying purpose of serving illidan. You also had the demons that were sworn to illidan serving him in shadowmoon valley as well. Nearly every boss in the expansion was taken from warcraft 3.
Gruul they made up.
Kharazhan was the home of Medivh, who was in WC3.
Magtheridon was from WC3.
Kael'thas was from WC3, Vashj was from WC3.
All of the caverns of time raid was just a recreation of the final battle in Warcraft 3 vanilla, including the hero units of the scourge returning as bosses you face.
Black temple brought back even more characters including Illidan, Akama, and Maiev. Even Teron Gorefiend who made his debut in Warcraft 2!
Then even after all that, you goto the sunwell to ultimately face Kiljaeden, also from Warcraft 3.
I mean the entire expansion felt like celebrity deathmatch.
And aside from boss battles, you got a bunch of orc history and such since that was their homeworld, you got to see Rexxar again (also from warcraft 3) although he was in vanilla he just wandering around in desolace doing nothing useful.
All in all, it was great because it was just such an epic throwback to the RTS games. Vanilla's bosses were all made up on the spot just for WOW and seemed completely random and arbitrary. Then after TBC when you move into Wrath of the Lich King, it was going to be all about wrapping up the bit with arthas and the scourge, but was kinda lame because you had all these pointless raids full of crap they made up on the spot before you ever even fought arthas. And the one other character they brought back, Anub'arak, was just a 5-man boss that insulted prettymuch everybody who was looking forward to him returning and being epic. Then when TOC came out (worst raid ever designed btw) they lobbed him in there as the final boss to try to make up for that, but he didn't even fit or make sense there and it was also such a huge, ridiculous disparity in power from where you could easily KILL him in a 5man vs needing 10 or 25 people where he was much, much stronger with many more abilities.
Another lore failing in wrath IMO was them farting out the vampire elves and de-emphasizing death knights' power. Death Knights were always commanders and generals in the scourge along with liches. Baron Rivendare in vanilla was a good example of what a death knight should be, an awesome end boss with tons of minions under his command. But in wrath, they farted out these ridiculous vampire elves out of nowhere and claimed they were like scourge lieutenants and held all the power in the scourge second to arthas and all this other nonsensical BS, then they had Death Knights running around as common trash enemies that commanded no troops, not even their own petty summons. Then they had the "Freed" death knights that served darion mograine be completely inept pansies and even made daily quests out of rescuing them from wooden cages. Ridiculous. They messed up all the DK lore in wrath as far as i'm concerned.
Then you have the fact that Arthas was in your face every 5 minutes in Wrath. Seemed like every other quest he'd pop out of a portal, shake his fist and be like "I'll get you next time !" then run away. It was so unbelievable and irritating. He might has well have been a companion character that just followed you around and commented on everything you did.
I could go on about cata and MOP, but i've said what was important about TBC being the best for story.