To be more specific, potentially they could lose their trademark (at least in the US) if it becomes an ordinary word ("google" isn't an English word yet, although "googol" is), as once a word has become a generic term, it becomes impossible to enforce trademark rights on it.
[Irouléguy] It would only become a generic if "to google" meant "to search on the internet on any search engine." As long as it's defined to mean "to use Google" it shouldn't present them with any problems. There are plenty of brand names which have become generic nouns, applied regardless of brand (escalator, tannoy, biro, etc.) but not many verbs ("to rollerblade" is another, though).
I don't think "escalate" quite counts as it predated "escalator." The thing which makes "escalator" a generic is the way it's use for any moving staircase, with no regard for whether it's an Otis "Escalator" model. If, however, you say, "I'm just going to escalate to the third floor, darling," then yes, "escalate" qualifies as a generic verb. Personally I've never heard it used that way.
"Escalate" no longer reads as a word to me, as a result of the previous paragraph. I just see a bunch of meaningless letters. It's annoying when that happens.