I think "to Google" as a verb for "to search on Google" is OK, but only informally. I use it myself. However, it has become synonymous with "to search on the Internet, regardless of search engine used" which plays into the hands of those evil corporate types.
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.
"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.
(Darren) Stare at any word long enough and it begins to look mis-spelt or foreign. Either way you think you're going slightly barmy. I can assure you you're not unless I am as well.