You got 2 completely different missions.
The first one, the one whit a map attached, asks you to destroy a "pirate hideout". Sometimes this is a difficult mission, because hideouts can possibly have 1 or more cannon tower and 10+ ships, with good capitains and AI...or be very simple, with only 3-4 damaged ships. But ehi, you have a map so you no longer need to waste time finding this nest, go and destroy everything!
The second one asks you to sink the admiral ship of that specific pirate (often the one noted in the chronology, e.g. "John Beneke attacked again") wandering in some places, he has no hideout, thats why you couldn't find anything. Tavern hints are not really credible, come on they are spies! The best you can do is to save before going to find him and reload if u can't. Could be a very easy mission...if you can find him!
Oh and one last thing.
The pirate you're expected to kill is already on the map, somewhere, BEFORE you accept the mission. The hideout, instead, is genereted AFTER you take the mission.