HereForTheBeer: The storm rings a bell but I'm drawing a blank. Been a while since I played.
Some of the missions aren't fully activated until you find more info about the encounter. For instance, suppose you get a piece of treasure map and you manage to find "X" with just that one piece. Well, you're required to find a few more pieces of the map before that location gets activated. Then, lo and behold, you go back to the spot and you find whatever it is you're looking for, even though you've been bumping around that area for a long time looking for the magic pixel.
Just to expand on this.
Storm quests can be a bit tricky. Storms continuously move very slowly, but if the location is a long way from where you picked up the quest, you may have to expand the area that you are searching, in case it has moved on by the time you reach it. Sometimes you just luck out, and it moves too far or disappear before you get to it. It's still worth doing these quests whenever you get the chance, as they are great for getting navigation skill points for your captain. This will help you navigate around/through storms faster.
Finding quest locations be they storms, sunken ships or other, can give somewhat vague directions at times. If they say its NW of a town, sometimes its nnw or nww or straight nw, and it may be a considerable distance from the town, in that direction. Sometimes you just luck out on finding it.
I half agree about the map pieces. Sometimes it wants all pieces found, and sometimes you can stumble across the location before you have even found the 'X' piece and still claim the reward. If it won;t let you activate it, feel free to get another map piece and try again, but most of the time you do not need to complete the map to get the reward.
Regarding your query about pirate ship quests a few posts above. You do need to remove a ship from your convoy in order to hand it over to the pirate. be aware that pirates will fill the ship to max cannon capacity, so do not give them a military frigate, as they won;t have any room left for looting cargo from other ships, and you will never get any money from them.