Sword and Skull (2005)

From the publisher, Avalon Hill:

Ahoy, Mateys!

That scurvy villain, the Pirate King, has stolen the Sea Hammer - only the pride of Her Majesty’s Royal Navy - and taken to the seas like the dog he is! It’s up to you to commission a brave officer of the Royal Navy to pursue that black-hearted cur, catch him, and turn him into shark bait. But he’s a rascal, that Pirate King, so you’ll need to recruit one of the dregs of the Queen’s dungeons because sometimes it takes a pirate to catch a pirate. Iffn’ you discover where that swab is hiding, you’ll need to beat the Pirate King in a duel or acquire enough gold to buy back the ship. Act with haste because you’re not alone in this hunt. Whoever saves the Sea Hammer first wins the Queen’s undying gratitude - and the game!

Here's a description of the game from Timothy Rose, who saw a presentation on the game at GenCon:

The "S&S" pirate game is a "track" based game (think "Talisman" more than "Monopoly" ). Each player controls two characters, a "hero" and a "scoundrel" type, and the goal is to retrieve the Queen's flagship from the Pirate King. Of course, each character has different ways to do that, either by derring-do and combat or by more underhanded methods (if you have enough gold, you could even BRIBE the Pirate King to get the ship back!). They showed the box design, pretty standard pirate/cutlass stuff, but nice art.