This is effectively a) putting everyone’s approximate search histories on the internet, or b) outlawing google search’s buisiness model.
The consequences of trying option a and failing even once are so great, I argue if that’s your goal you should ban logged out personalization before anyone deludes themselves into thinking they can do it without leaking everyone’s info publically. I also think that’s going to harm consumers more than it actually helps them but I am obviously biased as an ex google search engineer.
What about the legal risk for Google if you opted out of the tracking a month ago but now google thinks you are a different person and is tracking you?
https://motherboard.vice.com/en_us/article/78k8pz/how-you-mo...
They're also googles problems to solve, not societies. We're not required to provide solutions for them.
If google can't solve them, maybe that means google's business model is illegal.
The data subjects of ad networks however are completely different entities from their customers, which makes it a very different compliance problem. It might not be possible at all to conduct that kind of business in a compliant way.
In practice, legislation goes into effect globally by being in a large enough market that companies would rather comply than lock themselves out. Several companies have rolled out their GDPR compliance updates globally rather than just to the EU. It's the same reason that lots of products in the US comply with standards that only exist in California.