jgsugden said:
To an extent, instantaneous or ultrafast travel is a feature of high level adventuring. Anything you do to prevent them from doing it feels like you're stealing power from the PCs. Most players resent not being able to use the high level powers of their class. As such, I would recommend that you not try to eliminate this type of travel.
I agree. D&D shifts as you reach mid- high-levels, so that what were obstacles before are no longer relevent. Stone walls no longer hinder characters that can
fly. Great distances no longer slow down characters who can
teleport. The game evolves as you gain levels, so that former challenges are replaced by new ones. Trying to artificially make low-level challenges retain their difficulty in a high-level game is difficult and, ultimately, unsatisfying for the players who have worked to gain their abilities.
A campaign based on high adventure on the high seas should start at 1st-level and rise slowly, so that you get the most time in those low-levels where such obstacles remain. Indeed, you might design the campaign to end at 10th-level, so that it finishes at relatively the same time that the theme is played out. If you do decide to continue past mid levels, the challenges are going to change.
All of that said, there are still ways to make travel relevent for short periods of time. Jgsugden mentioned some magical means of limiting the ability of PCs to
teleport, by limiting the magic. This can work once or twice before the players start to get tired of it.
Another way to go about it is to present circumstances where teleportation isn't useful. Consider an adventure where the PCs are required to locate a nameless, ancient ghost ship. The ship cannot be scried, and moves about the open sea, meaning that the PCs will have to charter their own ship to seek it out on the high seas.
Or, simply shift the adventure to another plane, where the PCs don't know the lay of the land well-enough to teleport, and must therefore travel overland to progress across the countryside.