Possibly, but it still might not be possible for Google to provide a means to decline the ToS without issuing an update (which, as has been pointed out, wouldn't be possible to install anyway without accepting the ToS).

Then it's a device that does not comply the regulation and must not be sold.

Terrible for the environment. Lets apply rules with common sense [1]. As much I am for privacy this kind of interpretation is very bad.

1. https://study.com/academy/answer/summarize-all-about-a-dog-b...

The device could still be software-updated then sold, or sold outside the EU. Nobody is saying that it must be landfilled.

Sure, that argument could certainly be made. But unless someone is taken to court over this (or at the very least, threats are made), I think people will continue selling such phones. After all, most sellers aren't going to realise their products are in violation of the law.

If they flag compliant devices, it would be possible on the server side to limit data collected that comes in without the "GDPR-Compliant: true" flag.

Even if the ToS are pulled from the web, it might just pull the document, not the UI, providing opt-outs, etc

They could replace it with a document saying “There are no conditions of use. Enjoy your new phone!”