I agree with Lyan,
the concept, Zuul, is pretty good - searching allows you to find other things, not just ships, but random would be better - maybe even including (for more difficult levels) storms, etc which damage the ship.
Back to one of your ideas..., touching on a subject you mentioned below about burried treasure, would be the ability to buy a treasure map from the tavern - like on rare ocassions. Sort of like the "Rumor" function which when clicked brings a ? mark against the location it relates to. A Treasure map would bring up a X against the location and a seach function in that location would reveal the treasure. Maybe having a feature in this which costs you food or men while searching for it, etc, to make it more even.