Two complaints I saw a lot in BC were how we seemed to either kill off major lore figures or there was no clear idea who they were or why we were killing them. The first I don't know what to say about it except that knocking down three major WC3 figures was excessive, especially with how they were radically changed to justify it. The second, well that's all about the buildup.
Bosses cannot simply be stuck in the game. That makes them feel like they are bosses just to be bosses; loot bags. 5-man bosses are often like this along with most raid bosses beside sometimes the last few (for specific examples, take a random boss, odds are it has no apparent story to it). The proper method is to craft the boss, build it up, make it so that by the time players see it, they know who it is and exactly why it must be destroyed. A single quest doesn't do it. Even a chain isn't enough. You should see the effects of the boss long before you would possibly face them.
Ragnaros will be my example, mostly because he's perfect. When does an Alliance player first see Ragnaros? Most directly, when they first get anywhere near Blackrock Mountain and notice a massive scorched area and a huge volcano. You know something happened beyond a natural event; the devastation is too complete. If you don't see the mountain, go to the Wetlands and watch the fighting between the dwarves. See the Dark Iron dwarves? They are ruled by Ragnaros. You might not yet know of Ragnaros, but there's clearly some evil force at play.
As you move closer to the mountain you learn more. Scattered books tell the story of the war between the dwarf clans and the summoning of Ragnaros. Quests start to send you against the dwarves. You learn more over time.
For the Horde, it starts out on a smaller scale. Go kill this hostile fire elemental in Blackrock Mountain who seems to be working with the dwarves. From that you learn of Overmaster Pyron and are sent to kill him and recover a tablet. Then you first hear the name: Ragnaros. The Horde NPC gets scared. There never is a direct "go kill Ragnaros" quest. Instead you simply know of the threat and also that he probably has something powerful to take. The Hydraxian Waterlords send you into MC to fight their enemies: the fire elementals. Sadly, the elemental war doesn't get a lot of attention overall, only a handful of quests in the MC chain and some scattered elsewhere.
When you do finally face Ragnaros, despite not appearing in any previous lore, he doesn't feel as if he was added just to fill in a boss spot. He feels like he belongs, or like he really, really doesn't belong and we need to defeat him.