I think it's so cool you could in theory buy a satellite module eg. $250 break out board from spark fun, plug it in and be talking to a robot in the middle of the ocean. I wondered about the legal aspect, can you do that? Just release something into the wild.

Why not? I doubt there are any legal restrictions other than don't be a hazard to navigation. But it would probably be too small to be a hazard anyway, and likely too small to be noticed.

Yes you can. However, international waters are a physically challenging environment and getting there requires navigating national waters which have regulatory restrictions. Of course, enforcement is probably nonexistant if you're small, barely visible, and heading straight out to sea... so, solve the "invisible awesome robot that can survive in tough conditions" problem, stock the "multi-day batteries for energy continuity" load, buy the "expensive communications" solution, and then yeah - you too can play with the big boys in the bathtub. Or ... just stick to your actual bathtub.