As far as I know, he spawns in one spot on the map and stays there until you find him or enter a town or something. Go to the corner of the map and then face a cardinal direction and turn just the tiniest bit. Like one degree. Fly in a straight line and you'll eventually get him. :P