Possible counterpoint: their use as a generic is isolated within the US (maybe some other countries, but certainly not universal), whereas ‘google’ has arguably become a pretty global term (at least in the Anglophone world, and I believe in some other languages, too), so the reach is very different in scope.

(e.g. Despite Kleenex still a big brand in the UK, nobody uses it as a generic. The product is called a ‘tissue’)