The only long-term solution for long-distance communication I can find in the core rules would be a Rary's telepathic bond made permanent. That's a pretty pricey way of doing it, though: 13,800 gp (most of which goes toward compensating the caster for the loss of 2,500 XP), and requiring a 13th level caster.
It might be easier to get a cleric to make a wand of sending, but that's even pricier: 21,000 gp for a 50-charge wand, and requiring a cleric or wizard around to use it. After that, we get into some seriously pricey things, like a crystal ball (even a visual-only ball could be used to receive visual messages).
If your campaign includes psionics, the king (or other "communication hub") can employ a psion with the correspond power, which lets the manifester form a two-way link with anyone he has met before as long as they are on the same plane. It only lasts for one round per level, though. It's a 4th level power, so it's probably not practical to equip each vessel with someone who can manifest it, but it is useful for the king to ask his admirals how they're doing.