Here's a list of words that have gone into the public domain via genericide, or the loss of trademark protection by the ubiquitousness of the term. These words were originally trademarks, but they were so successful that they named the product for all time - the danger of a perfect name.
Some say "Google" is on its way to genericide because of the way it's used as verb for "searching." Personally I think it's safe for now. When I say I'm going to "google" something, I don't use Yahoo! to do it. Do you?
I recall reading (but forget where) about how word processing programs assist in the maintenance of trademarks by auto-format capitalizing the first letter of major brand names. The idea being that a capitalized proper noun is more trademark-y than a regular word. Similarly, if you type "google" in MS Word, it will be red-underlined; the suggested correction is "Google."