I used to do the same thing he does, you can find people easier and faster than seems possible if you're prepared to heal refresh infinitely, recall a lot and possibly teleport to cover more ground if you're really greedy and conclude you made too much distance.

That said I'm not denying he could have been helped.

First one, checks desert, yep, road to Oryx is low mvs so I'd check that too.

Finds you at tower. Yep. (People go here and if you catch them in the maze they're boned.)

Finds you at Gol'Galath, yep. (easy check off north road)*

Finds you at tower again, yep. Why? Last time you tele'd you went to HToS, I would check too.

You explain Huntress.

Outlying villages is right next to the Tree so I don't expect something different here.

As for the canteen, sounds like it wasn't your day. :p

*edit: no udgaard recall, forgot he's an outtie