I did the cleanup route on my Vista Home Premium PC and have it rather pristine now. However, if anything goes wrong, I don't have a systemic backup. I usually buy my own copy of the OS at a later time (usually after SP1 is out) so that I can do a fresh install and I remove all the partitions off the HDD at that time as well.

So, yes, clean install is better, if you have the time and means.