This is something that seems very doable. Bear in mind that I have very little experience in these "open world" games so what I'm going to propose might not be practical, but I do hope it is logical.
I would make one small change in that if ship A plans a deep sea voyage at the same time as ship B, that there be a mathematical chance (abet a small one) that the server determines that they have encountered each other and deck mode is engaged for the captains to do whatever they decide that they will do, pass quietly, flee or fight. The encounter might be nothing more than a sail on the horizon, or it might be a course that brings them much closer. Chance (like fate) decides.