I've decided to rethink the ship sailing mechanics. There are several options
1. When a party visits a city with a shipyard, it can buy/rent a ship. Such ship will be shown like a usual roster unit, but wont be present in battle. It will have an inventory, which could only be accessed while in sea. Such ships can be traded between parties. This system still doesn't accommodate for a ship being bound to some single sea. But it is, well, simple.
2. Warcraft 2/Heroes of Might & Magic system. Like above, but the ship will be left on in the sea, when party disembarks. This system accommodates for several seas. Yet since the world map is randomly generated, it is not that useful and makes AI much harder to implement. Both Warcraft 2 and HOMM games had notoriously bad ship AIs (proper AI requires building a zone connectivity graph). And it resulted in a few crazy twists, like some party ending up landlocked, after its ship gets stolen or sunken. In HoMM games there is a low level spell "Scuttle Boat", which was used to trick and landlocked larger AI armies. I still don't get why one needs magic to damage a ship
Many HoMM maps explicitly relied that the player will seize a boat from a disembarked AI party, which in some cases got stuck in a loop and failed to disembark (or disembarked at a wrong place), soft locking the whole game.
3. Some games, like Ogre Battle and Warlords, allow parties entering the sea even without a ship, but greatly slow down the movement, unless the party has some flyer or ship like units (i.e. octopus).
So yeah, picking anything here is a trade-off.