What is notable about the examples given above is that Kleenex, Xerox, Hoover and Walkman are brand names or trademarks, but the names have become common nouns because of their popular usage to refer to the generic name of the product. One can say 'pass me some Kleenex' to mean 'pass me some tissue paper', and likewise, Xerox means photocopy, Hoover a vacuum cleaner, and Walkman a portable music player. Xerox and Hoover can also be used as verbs.
'Just leave the broken pieces there, I'll Hoover them right away.'
Walkman, officially, only refers to portable music players made by Sony, but most people use it to refer to portable music players no matter if it is a product of KENWOOD.
These are called genericide, a legal term, which refers to once brand names or trademarks turned into common nouns. They have not lost their validity as proper trademark nouns but they have died as trademarks. They refer to not only their brands but also to same functioning products made by other companies. That's why the term has -cide ending.
It is ironic for the companies - the products have become so well known and popularly used but the brands name or the trademarks have also become too popular that they can refer to other products. The companies try in every way to stop the genericide of their brand names or trademarks.
Becoming too popular can be a double-edged sword.