What is the starting quest to get this recipe? It's not Never Ask Me About My Business.

it should be noted that the quest requires you to be at least Neutral with https://vanillawowdb.com/?faction=910 Brood of Nozdormu in order to get the quest...

There is quite an involved chain required to get this recipe. It is part of the chain required to open the gates to Ahn'Qiraj, but it is still possible to complete even after the gates have been opened. It begins in Silithus with Baristolth in Cenarion Hold.

Part 1 - Getting Neutral with https://vanillawowdb.com/?faction=910 Brood of Nozdormu
1) https://vanillawowdb.com/?quest=8286 What Tomorrow Brings - talk to Anachronos in Tanaris
2) https://vanillawowdb.com/?quest=8288 Only One May Rise - kill https://vanillawowdb.com/?npc=12017 Broodlord Lashlayer, 3rd boss in BWL. The head can now be looted by everyone present.
3) https://vanillawowdb.com/?quest=8301 The Path of the Righteous - collect Silithis Carapaces. Repeatable until Neutral.

Part 2 - A Bit of History
1) https://vanillawowdb.com/?quest=8303 Anachronos - talk to Anachronos
2) https://vanillawowdb.com/?quest=8305 Long Forgotten Memories - go to Silithus, find a crystal
3) https://vanillawowdb.com/?quest=8519 A Pawn on the Eternal Board - watch event, return to Anachronos
4) https://vanillawowdb.com/?quest=8555 The Charge of the Dragonflights - opens three quest chains. We want the Blue Shard chain.

Part 3 - The Blue Shard
1) https://vanillawowdb.com/?quest=8575 Azuregos's Magical Ledger - begins in Azshara with Azuregos (or Spirit of Azuregos, if Azuregos is dead)
2) https://vanillawowdb.com/?quest=8576 Translating the Ledger - talk to Narain Soothfancy in Tanaris. Opens 3 more quest chains. The one we want is:

Part 4 - The 500 pound Chicken
1) https://vanillawowdb.com/?quest=8584 Never Ask Me About My Business - talk to Dirge Quikcleave in Gadgetzan
2) https://vanillawowdb.com/?quest=8585 The Isle of Dread! - go to the Isle of Dread in Feralas, kill (lots of) stuff
3) https://vanillawowdb.com/?quest=8586 Dirge's Kickin' Chimaerok Chops - bring dirge some rocket fuel and deeprock salt (yum!)

Finally, you are rewarded with https://vanillawowdb.com/?item=21025 Recipe: Dirge's Kickin' Chimaerok Chops!

Post-4.0 update: Sadly, this excellent quest chain was removed with Cataclysm. This is still the only Epic-quality cooking recipe in the game. The only way to get this recipe now is by acquiring it from someone else who had already completed the chain; as the limited supply has dwindled, the auction house prices have risen quite high! If you are a collector, this will soon be almost impossible to acquire - you can always replace the gold you need to buy the recipe (if you can find it), but no one can farm more of these recipes.

Even more sadly, the Isle of Dread has sunk (as it's only purpose was as part of the Scepter of the Sands quest chain), and it is no longer possible to obtain the Chimaerok Tenderloins needed to cook these delicious chops (as they only dropped from mobs on the Isle of Dread). Count yourself lucky if you've had the chance to sample some!

I finally got this book after about 6 months. When 3.0 first came out and I saw the achievement system, then researched here (Gorbal's post above would have saved me a lot of time!) and realized I had a long way to go. For one thing I started WOW during BC and never got into any AQ raids and skipped Silithus completely.

There was a few PUG AQ40 but the reps return back then was lousy due to being level 80 (diminishing reps was removed a few patches later GRRRR) and ended up doing various quests both outside and inside including token turn ins and old token tier armors. It was still slow going until Blizzard dropped the diminishing reps gain, then I rocketed to neutral, and jumped through friendly to mid part of honored when I was allowed to complete the token quests. That was about a month ago. But a BWL raid stalled me.

Today I got into a BWL PUG that wasn't fail, and got the head. Later afterward, I finally got down with free time and decided to try and finish the whole thing. 5 hours of zone hopping, switching between WOW and Wowhead.com for references, several hearth stones to dalaran for quicker routes, I finally got the book!

The hardest part was getting the 500 pound chicken stuff. Lakmaeran's Carcass was a tad easy but slow for level 80 moonkin in half PVP half heroic gears. I used innervate once, healed myself twice, but I didn't need to use potions. Getting 20 Chimaerok Tenderloin also took some time, I had to do 2 clears of the island to get all 20, about 40 minutes total (10 minutes clearing, 20 minutes before the first ones respawned, then 10 more minutes clearing again). The drop rate for the Tenderloin was about 1 in 3 despite what Wowhead says.

Now off to giggle like a school kid with key to candy shop. 162 recipes learned in my cook book (thistle Tea being the only one I don't have for obvious reason) I also posted in suggestion forum to make learning this recipe a FOS achievement because it takes so long, required multiple zone hopping, reps grinding with old world rep, raiding in another old world dungeon to get it. Anyone who rolled after BC expansion's release is not likely to have the reps with Brood of Nozdormu required to start this chain of quest.

With the exception of BWL raid, everything could be soloed but I do suggest going for AQ40 raids whenever possible as the reps are much faster than spending couple hours farming bugs. (plus chance at 4 more mounts toward mount achievement, a FoS achievement for red mount, and more quests done toward loremaster!)