Another GSM-on-ship operator is the Norwegian operator MCP, MCP Maritime Communications Partner AS, MCC+MNC = 901 12
For the list of served ships see
http://www.mcpinc.biz/coverage.php
I know 901 is not the correct MCC for Norway, but this company operates only onboard ships, hence the use of a different MCC is probably set to prevent confusion in billing systems like the ones AndreA experienced.
If I read the tariffs correctly, Vodafone customers pay 2euro/min outgoing calls, 1euro/min incoming calls (which is about twice the usual tariff for roaming in Norway)