This is the route I took - This is for the alliance.
Eastern Kingdoms. Start at Booty Bay. - There isn't really a tricky inn to spot here, for the dwarf inns though, it's hard to see, it's in the little kiosk thing where the innkeeper is. Don't forget Kharanos, which is just out of Ironforge!!

Kalimdor. Start at Darnassus. - Pretty much the same. Ask a guard in the Exodar for the Inn, it was hard to find for me - Same for Darnassus, it's in Craftsmen's Terrace. Ask a guard if you need directions.

Outland. Start at Honor Hold - All fairly easy, the Shattrath Inn is either ALDOR or SCRYER, on their respective tiers. I did this on an epic flyer, It's designed to be flown manually, but you can pretty much do the

Go go, get those candies!
Changelog:
Code:
10-19-09. Fixed a mistake in Outland Map