Maybe they could be allowed to build a both "western" and an "eastern" port at the same time and then be able to raise fleet levies separately for each? Although I admit that would probably be quite hard to program. Maybe different holdings can provide vessels for different sides, although then you'd have to telegraph which holdings makes what ships somehow...then what about the (admittedly few ... 2? ... 3?) countries that border the Red Sea and the Mediterranian?
Although I checked and only one county (Farama) actually borders both seas, so the whole thing can be solved by splitting it up or changing it's borders a little.