Right on cue, Slashdot reports that "Google Sends Legal Threats to Media Organizations" over the use of its name as a verb for internet searces. See here.
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.