> This will take weeks to clean, and that's just for Google.

Couldn't Google just purge all cached documents which match any Cloudflare header? This will probably purge a lot of false positives, but it's just cached data, so would that loss really matter? My guess is that this approach should not take more than a few hours on Google's infrastructure.

Of course, this leaves the problem of all the other non-Google caches out there.