Did you go use the rock in prosimy before pledging. If so, did you fill your water container there? If so, that's bad water.

Also. It's not like you teleported that far away each of those times, and one time was a repeat area you had been in recently. AND the last time you teleported that was the eastern continent so there's a LOT less areas to check there.

And like someone already mentioned, he does have windwalk. VROOM VROOM! ;) Try not to let it get you down. It's easy to wonder how the fuk someone can find you like that. REALLY good and relentless PKers are like this. Not everyone is on that level.