It's definitely considered damaging to the brand when the name is "genericized." It obviously happens often, with many great examples in this thread. The interesting thing (to me, at least, as a lawyer with an academic interest in IP law) is that is is reversible, albeit with extreme difficulty. According to research, most people say "photocopy" now, or just "copy," whereas 15 years ago most people said "Xerox."
The really interesting thing is that it's not at all clear that Xerox's efforts to end the practice actually had any effect ... it seems, instead, that the public just, for lack of a better phrase, consensually decided to drop "Xerox" in favor of "photocopy." My own opinion is that if the public is given a suitably descriptive word for a newish process or product, they'll use it over a brand name; thus "photocopy."
Oh, and while I obviously can't speak to how things will be, for right now when people say they "googled" something, my impression is that they actually used Google. I won't be surprised, however, if Google at some point uses its considerable clout to propogate a new word or phrase to avoid dilution of the Google brand. Something like "i-search" or "web search."