That's the great thing about marine sanctuaries. You agree upon a region in the middle of the ocean to declare off-limits for fishing. The fish population of those regions repopulates the rest of the ocean, and you have the best of both words. Unrestrained fishing, and stable fish stocks. You can even find perpetrators using satellites, which helps with enforcement.
The hard part is agreeing upon regions both large enough and spanning enough biomes.