First, let me say I know there are other ways of doing this, most notably the undead pirate mobs in Wetlands which is a bit inconvenient for Horde to go all the way there. Since 4.0.3a, there's an easier way for Horde.
1. Get the level 17 quest The Blackmaw Doublecross from Haggrum Bloodfist in Azshara
2. Use the provided Ambassador Disguise
3. Shift into Moonkin form and mount up
4. Click the disguise buff off
Completing the quest will lose the disguise item. Also note that the item only has a 1 hour duration. So, once you lose it you will have to abandon and re-obtain the quest to do this again. Still quite easier than traveling all the way to Wetlands, since most Horde will be hanging around next door in Orgrimmar.