Got some problems with this kinda quest too. Maybe It's a bit off the topic but here goes. I took 2 quests of finding the stolen ships and kidnapped bride. So i travelled a lot but no sight of those 2 ships. Then suddenly when i made port in Port Royal, i saw an unsual guy (like the officers in the tavern) so i talked to him. Turns out that's the guy with the ship i've been looking for. What's weird is he was on the island not setting sail away for other one, even though the local port controller gave me the information that the captain set sail away 'bout 20 days b4 my arrival (weird isn't it?). Then i went back to the world map, sailed around for a while, 'bout 1 week, and voila, the bastard turned up right out of Port Royal (WTF?). Still, i boarded the ship and returned the quest.
Second quest happend just like the first one when i was looking a for guy with the kidnapped bride who i couldn't find anywhere else, then he turned up in port au prince (on land). Talked to him, got declined just like the last guy did. So i tried the same way that worked out for the first time but this time it didn't work. I waited in world map around the port for like 2 weeks, lots of encouters happended but no sight of him. The quest is yet to be completed and i guess this is some kinda random bug. I always used head to the port controllers or random citizens in every port to get these kinda quests as they give a big boost of repuation towards a nation including big booty too. But now thanks to this one, I started a new game and will never take these kinda jobs again.
PS: one little thing is that in both cases, after talking to the indicated captain, i tried going to sea mode and looked around in the port but no sight of their ships either.