Yeah, ain't that WinRot a b!+@h?
I've almost always noticed an improvement with a fresh install over cleaning out files/defragging. Maybe it's psychological, how would I know? But even if you remove files and uninstall stuff, your registry is seldom changed. Guess what gets loaded when you boot your comp? Among other things, the registry!
If possible, ghost your image before you reload a new OS, in case of problems. If you load with no problems, then ghost after fresh OS install, in case you get a pestilent virus (even with anti-virus software) later on. I have a ghost image for both my computers and it is NICE to have a fresh OS, ready to go, in about 30 minutes.