Spoiler: Bug report shows part of a 76% revealed map And now with nothing changed other than hitting the Sea Serpent along the way (Tavern was already full, no Academy / Voodoo Hut skills finished in the meantime), the chance of success upgrades from Suicidal to Dangerous.
I you look closely your first journey goes through more dark water (making it a longer trip compared to the second journey) - perhaps tired pirates won't fight as well after a long journey!