I do Both, Clean and reinstall. I clean most of the time and reinstall some of the time when I fell like I can't clean anymore, especially when the computer gets really draggy and stuff.
But most of the time after I reinstall everything, it's back to almost before I reformated except it runs a little better.

Lets see, I go into the registry, delete unwanted, scan it with some spyware registry cleaner, then uninstall it, and remove it completely, gone, poof, natta. Scandisk, Defrag you know the rest.
gotta be clean, organize, messy but simple.