Apparently it's a bug. I've found several so far, luckily Paradox is quick with patching stuff and they have a very active community the devs are participating in themselves. Maybe a good lesson for Firaxis.
Something that puzzled me is why trade didn't leave the Cape of good hope trade node, as it's unidirectional. Once I send a trader there to kickstart it, the problem was solved and I could recall the merchant.
This bug is quite funny:
My ships are on a mission in the Gulf of Aden, but they want to repair in Malta since that's the closest province from the Red Sea. Did I mention I hate AI pathfinding in about every game? It's the reason I stopped playing Total War games, I can't stand microing every unit through the city gate.