Specifically there are 8 towns that have fishmongers - you can do one quest from each, but your ship has to be on the same sub-server as the fishmonger you are talking to, in order to receive or complete a quest.
So, to get a quest from the Britain Fishmonger, your boat must be on the same subserver as Britain (which means roughly north of the moongate, but further south than the server line that runs between the city, along the edge of the mountains, south of the Bog of Desolation, and west of the server line that runs north/south just west of Vesper)
If that quest is delivered to Papua, you have to use the serpent pillar to get to the lost lands, to deliver.
Note that you don't have to be anywhere NEAR the docks, let alone the fishmonger. Only at the Sea Market should congestion be a real issue.
In fact, due to the way this is set up, as long as your ship is at Jhelom, Skara Brae, or Trinsic, you can recall around to all three cities and make deliveries and pick up quests, and save ship travel time.