What's installed itself in the registry? That's not permanent; it's a fixable problem. A utility like RegClean can do wonders for getting rid of annoying leftovers.
However, reformatting your computer every year or so is a pretty good idea anyway to get rid of the sludge.