I have a mission to find a sunken ship off the coast of Maracaibo. It says it's just off the coast not even a day's sail but I have no idea how I'm supposed to find it. Any help would be appreciated.

Pull out a real world map of the Carribean and look.

so it's not marked at all? I can find the town without a problem and sail east but nothing happens.

What I meant must have been that many places are not marked on the ingame map before you have discovered them.

Whether the sunken ship was shown in some way or not, I cannot remember as by now it has been quite a long time since I played the game. Sorry about that.