Assuming that it is gone, this story is possibly the biggest loss that Deathwing will inflict on Azeroth.
In terms of poorly designed quest structure, this quest is right up there with LOTRO's notorious Tomb of Elendil quest.
First, the player must complete all of the solo quests in Garadar, along with a handful of non-instanced quests for small groups of level 68 players in the western end of the zone. (Good luck finding a group for these, as level 68 players will receive far superior loot by going to Northrend instead of sticking around Outland.) This opens up a few more solo quests, followed by a visit to the 5-man Auchenai Crypts.
The Crypts are tuned for levels 65-67, though I guess that the original intent might have been that some players would run the dungeon as a level 70 heroic. The good news here is that the random dungeon-finder ensures that there will be players willing to fill out your dungeon group in exchange for random rewards.
To add a parting insult, however, the final step after the dungeon run is another non-instanced group quest. This is the exact same flaw with the LOTRO Tomb of Elendil line - the sheer number of prerequisites drastically reduces the number of players who would be at all interested in teaming up for this final step. (The other non-instanced group quests do not have any pre-requisites, so any players who happen to be in the area can immediately jump in if someone is looking for help.)
In short, finishing this questline at the apporpriate level in an out-dated expansion would not be fun for anyone who does not have a static group of some sort helping them out.
Fortunately for my hopes of ever seeing the end of this story, WoW has had far more gear inflation than LOTRO over the last three years. I was able to solo all of the non-instanced steps up to the Crypts run at level 78, but the final boss of the Crypts was a bit too much. Two levels and a bunch of gear upgrades later, the dungeon was relatively easy to solo.
The final step was obviously very easy to solo at this excessive level, but it would have been hugely frustrating had I been working on this quest at level 68.
... For a unique reward
As an Alliance player, I had been aware that this storyline would ultimately bring Thrall to Outland in order to tell the tale of the redemption of Grom Hellscream to his despondent son, Garrosh. As thanks, the younger Hellscream has gone on to become the annoying sidekick of the expansion, and there are people who would rather follow the famous corpse of Mankrik's wife than Garrosh as the Horde's new Warchief.
What I did not know was that there was something else in the story for Thrall. Upon completing all of the quests and failing to get Garrosh up off his rear end, the Mag'har Greatmother laments the absense of her son, Durotan. This name is meant to ring a bell - by the end of Warcraft III, Thrall has named the new Horde's homeland Durotar, after his late father. By doing what we normally do as adventurers, slaughtering our way across the zone, us players have inadvertently reunited the Warchief with his grandmother.
Players have some close brushes with the lore in various places in WoW. The Alliance has the now mostly removed storyline of the "missing diplomat" and Onyxia's stint as Lady Katrina Prestor in the very throne room of Stormwind. In Northrend, the Alliance reunites Muradin Bronzebeard with his brother. Horde players can hear a haunting melody by returning a keepsake to Lady Sylvanas. Both sides experience the battles of the Wrathgate and the Undercity (the latter of which will be gone in Cataclysm).
In these dramatic moments, though, it feels like the player serves in a supporting role to the real protagonists. We may provide crucial intelligence and support, but the final battle is fought under the banners of Bolvar Fordragon or Thrall or some other more significant character, with the player serving as a mere footsolier. Though it is ultimately Thrall that returns Garrosh's resolve, this story succeeds in making the player feel that it was our actions that led the Warchief to return home.
Getting this story done before the increasingly imminent Cataclysm was my highest in-game priority in MMO's, and the payoff turns out to have been well worth it. If you have never seen the tale and you have a character anywhere near the appropriate level on the Horde side, I'd advise you to do what it takes to see this story unfold before it's too late.
On the left, the legendary Doomhammer, weapon of prophecy. On the right, a hammer I picked up off of a random Flesh Giant who forges weapons for the Lich King's grunts in the Pit of Saron. Fill in your favorite joke about players and/or item designers overcompensating here.