True story: Hiroo Onoda, 2nd lieutenant in the Japanese army during WWII, finally surrendered in 1974.
More relevantly the Confederate Ship Shenandoah was commissioned in 1864 in England, sailed round the Cape of Good Hope to Australia, then went north into the Arctic to raid the Union whaling fleets on the 5th of July, 1865.
On August 2nd, 1865 they attempted to raid the English ship Barracuda, only to find their commission and letters of marque were no longer valid since the Civil War had ended. By all accounts everyone was a little embarrassed.
The Emperor of Bael Turath comissioned the Black Storm as a large and powerful warship, then sent his best wizards to work dark rituals over it to strengthen it, to bind devils to it for a crew, and perhaps even to sail into the Shadowfell, the Astral Plane, or the seas of the Feywild.
It was turned loose with instructions to raid vessels and ports not flying the Turathi ensign.
Sadly, Bael Turath hasn't commissioned a vessel for about 5,000 years, so at this point everyone and everything is fair game.
The Black Storm has been at sea for a long, long time: stories of it are rare because it tends not to leave survivors. The devils are bound to the ship as long as it remains intact: while normally this would result in the captain crashing the ship into a reef as soon as his diabolic interest in piracy waned, being allowed to cruise around the mortal plane terrorizing innocents and stealing stuff is a pretty congenial job for a devil, so he's kept to the spirit of the agreement.
There's surely a few other ways to abort the binding ritual: those things always have freedom conditions, All you'll need to do is recover the original comission and letters of marque. Those should only be in the haunted ruins of Bael Turath's capital, deep in the library....
The party can either attempt to destroy the Black Storm (which should be a serious challenge) or try to find out its orders and commission in some obscure dungeon or other...then exploit them to banish the devils.
