What is the most optimal way to visit all races' starting territories?
At level 70 you'll have a hard time getting them all. This is as close as you can get:
- Try to collect all Alliance races directly in Stormwind.
- Fly from Stormwind down to Booty Bay. There are a lot of people questing in Elwynn, Westfall, Stranglethorn and they're all very close to each others, Alliance and Horde alike (especially in both Stranglethorns).
- From Booty Bay you can take the ship to Ratchet.
- From there you can visit the Orcs and Tauren in their starting areas as well as search the Barrens for possible victims, which are quite popular as well.
- Hearth back to Stormwind and use the Deeprun Tram to Ironforge. From there you'll have to fly up to Tirisfal (Undead) and/or Eversong/Ghostlands (Blood Elves)
- Visit Hellfire Peninsula from time to time and check for people leveling there. There's a portal back to Stormwind at the entrance, making it easy to travel between both.
- Same with Dalaran (Northrend). It's also a good idea to have your Hearthstone here, because you have more options to travel around from here (at least at level 70).
- If it still works: PVP. Join random battlegrounds and poke them there. Rogues and PVP are a good combination and you'll almost always have a few of them with you.
In northrend at Valliance Keep there is a Quest Friends in Dalaran it will help you go to dalaran, which you can find there a portals into the main cities of Allied Races.