The reason international waters existed in the first place is because until fairly recently, no nation had the ability to reliably enforce claims to ocean territory unless it was very close to land (coastal territorial waters) or behind a narrow bottleneck (internal waters). Even making a token attempt to try to enforce a claim to deep ocean would be far more expensive than the benefits of such a claim.
Near shore you have the following benefits to territorial enforcement:
- Coast watchers -- Before the 20th century, spotting a ship could only be done visually. Deep at sea, you need another ship within a few miles of it. Within line of sight of the coast, you just need a guy with a lawn chair, a pair of binoculars, and a way to send word when he spots something. More recently, airplanes and radar increased spotting range over the horizon (both for ships and sea and for coast watchers), and eventually satellites allowed continuous monitoring of deep ocean, at least for countries with the ability to launch satellites.
- Shore batteries -- You don't just have to find the trespassing ships. You also need to do something about it. Warships are expensive, but stationing cannons and gun crews along important stretches of coast is relatively cheap.
- Coastal defense forces -- It's a lot cheaper to build a warship for coast defense than to build one to operate on the high seas. It doesn't need to be able to weather a storm at sea (coastal waters are generally milder, and if a storm does show up there's always a safe harbor close at hand), it doesn't need to carry as much fuel and supplies since it's only expected to be at sea for a few hours at a time, and it can be more lightly built and armored because it can always retreat to the shelter of shore batteries if overmatched.
The old three-mile limit for coast territorial waters was based on the maximum effective range of shore batteries at the time, and it's been gradually extended since WW2 (to five, then seven, then twelve miles). Your map shows the 200 mile
exclusive economic zone, where countries claim mineral and fishing rights but generally don't try to impose restrictions of passage of shipping.
Laying claim to deep ocean would be nigh on impossible before the Napoleonic era at the very earliest, and still very difficult well into the 20th century. By the time it even begins to be feasible, though, there's a number of countries that have trade on the high seas as a major part of their economy, and those countries also tend to be the ones with big navies (to defend their trading interests, suppress piracy, and contest attempts to blockade their ports in wartime). The countries with the best ability to project force into deep ocean are the ones with the most to lose if
other countries decide to do the same thing, so 1) they're unlikely to move first for fear of establishing a precedent or triggering a scramble to claim territory, and 2) they're the most likely and best equipped to use "freedom of the seas" as a casus belli if another country lays claim to deep ocean territory.
The best option I can think of to overcome these difficulties would be for a single country that has worldwide naval dominance to decide it's in their strategic interests to lay claim to large chunks of deep ocean, probably Britain during the Napoleonic wars. They might be able to make it stick for a while, particularly if they don't give other countries too much cause to fight it (sticking fairly close to their historical policy of allowing peaceful transit and just fighting piracy, the slave trade, and warships that threaten British interests, but under a legal theory of territorial claims rather the OTL legal theory that pirates and slave traders were
hostis humani generis). This would break down eventually (probably the first time it was seriously challenged by a country with a significant navy of its own), but once the principle is established you could see overlapping, sporadically-enforced rival claims over deep ocean, gradually being sorted out into true territorial waters as technology makes enforcement practical.