But in a voluntary system, the oil company does not have to pay for anything. Say the company does not pay, it was the company's property and it was just trying to make a profit. Why should they care about the fish, the fishermen, the workers, and the surrounding environment?
That seems like a pretty big injustice to everyone affected. Since their is no government to ensure that justice is done, does it really go to what theymos suggested? (Literal) corporate warfare? Heads will roll? Potentially innocent people will die?
Well, firstly, the fishing company and the shipping company aren't going to buy the waterspace in partnership with the oil company without knowing that something like this might happen (that you are able to predict the possibility makes that quite clear). So, they'd have a contract requiring damages to be paid in the event of an accident (This contract would go both ways, of course - should the shipping company run into the oil platform, or the fishing company tangle something up with their nets, they would be required to pay damages, too).
Even without that agreement, the oil company surely realizes that literal corporate warfare is much more expensive than dealing with problems peacefully, and so they have an agreement that any disputes they have with other people would be handled by arbiters. In arbitration, the two parties come to an agreement, with the help of the arbiter, and the settlement is decided that way.
If the company decides that paying out settlements will indeed break them, and they refuse, and also refuse arbitration, then yes, it might indeed come to corporate warfare. Innocent lives might indeed be lost. Both sides know this fact, though, so it gives them incentive not to push it that far. The damaged parties might take smaller settlements, or split it up into payments, so that they get them, rather than running the company into the ground.
Violently extracting payments from people who have damaged you is inefficient and dangerous, and everyone knows this, so it's not too likely to happen. It might, but it's far from the first option.
How do oceans come into private ownership?
Well, you bring up a good point. You can't really do much to "mix your labor" with the sea to get something new, which you own. You can, however, mark it off, and there's always the seabed that you
can transform, in almost every way you can transform dry land. And just like in dry land, you can claim ownership of the livestock on that land - or in this case, the sea - and mark off the range with buoys. The water is, in this way, similar to the air above your land - if you could walk up into the air and fly around, and so could your cows.
Maybe the speech will change my mind. 
