You'd have to think that the trademark would be sufficiently diluted by common usage by now that it was heading rapidly towards invalidation (cf hoover, xerox, etc.)

You go ahead and start selling copiers branded Xerox and tell us how diluted that trademark is. It may be a common term, same as 'googling', but the test here is whether the company is willing to actively defend the trademark. I can assure you that all of the companies you mentioned would certainly have lawyers ready to prove they hold a valid trademark.