Yeah, the only real solution is to eliminate commons.

In case of the ocean I would say that every country should have the economic right to all points in the ocean closer to them than to any other country. Everyone else gets free passage (subject to your reasonable environmental laws) and to engage in scientific operations, but only the country has any right to remove anything beyond scientific samples.

It's not perfect given that some species move about, but it would go a long ways towards controlling the problem.