Always good to go the horse's mouth so to speak to answer these kind of questions.
Earllier I mentioned that to operate in international waters you would need Ship's Station License, but there were a few nuances. If you travel in international waters from one US port to another, you do not need a Ship's Station License. However, if you travel in international waters and make contact with a foreign country, then you do need a license. See: FCC: Wireless Services: Ship Radio Stations: Licensing
The FCC defines when a Restricted Radiotelephone Operator Permit is not required, if your use is not specified, then a RRO is required. See: Commercial Radio Operator License Program: Types of Licenses: Restricted Radiotelephone
Agreed on the ship's license (though I still wonder who would check these things). Concerning the RR permit, though, it's Canada regs that come into play here. They are the ones who require visitors to have an ROC permit to operate a vhf in Canadian waters. Americans cannot get a Canadian ROC permit, but Canada accepts the US equivalent (the RR permit from the FCC). I posted the link to the Canadian regs in my post further up in this page. Again, I've never been asked for my ROC permit, when up in Canadian waters, but it would be an easy thing for them to do. Canadian regs, though, make no mention of requiring a ships station license for visitors (not that I've ever been able to find).