BOAT SOLUTION BELOW
I played U3 this week for the first time since the Apple II days, found myself going crazy trying to find a boat (got up to over 200k moves and had one player at level 22...still no boat).
I had no luck finding answers online, though I must say the idea of eliminating valid land squares is an excellent idea and I'm sure it would have worked eventually. I tried it for a few hours and then I remembered a trick from long ago.....
The auto-save feature can be manipulated to produce as many boats as you want for the cost of resurrecting a character. All you need to do is board the boat in Lord British's castle*, attack the guard who follows you out there, let one of your characters get killed and then close the window U3 is running in. The auto-save feature will record the fact your on a boat, have a dead player etc. and when you reload the game you'll be in a boat literally on top of Lord British's castle. Save the game again, and sail away.
I know I'm 7 years or so late on this thread, but if I found it looking for the answer, I figured others might, and nobody should have to spend hours and hours and hours waiting for a boat just to continue the game (especially frustrating when you know the game well, you know you're stuck until you find a boat, and you would rather have fun attacking guards and dungeon crawling to build up your characters rather than endless orcs etc. roaming the coastline).
*Finding the boat outside LB's castle is well known, but if anybody needs the info on that, here it is. Go to the throne room, unlock the door on the west side of the room. As soon as the hallway turns North, go north until you see another door to the west, leading to the outside of the castle. Unlock the door and head west along the moat, then south....you'll eventually come to a boat you can board.