Some of the ships have era/faction settings for mercenary status in the unit prod file, I don't build inns so I can't say I've ever seen a ship on offer though. With respect to the bribing/retraining, I'm guessing the problem is the sea region. You can't move a ship into a province for retraining, and you can't move agents onto sea regions to do their abilities.