Can you prove that?
If so, this could be a very hot potato.
If google states "Your web history is currently empty" and "web history is paused" but they continue to track your searches in a way that is tied to your identity then I think they're in breach of several laws.
They could chose to withold the ability to disable tracking. But by giving you the impression that they're not tracking you I think they're definitely across the line if they continue to track you in spite of that.
> Google retains a complete history of your interactions with them, which is not subject to this Web History setting, not deletable, not removable, and will be shared across its properties.
Is a pretty heavy accusation to make without hard proof. And if it turns out to be true I'd hate to be the one to have to explain to the EU regulatory body how "your search history is empty" can co-exist with "we have a complete history of your activity". If it is a history on my activity then my search history can not be empty and if it is empty then google should no longer have it either.