There's a lot to be said for both cleaning and reformatting, you can always do both.
That way you gain some knowledge in both areas.
I also believe that manual cleaning by deletion of files and or removal of entries with HJT does not necessarily complete the job properly.
I even have my doubts about so called cleaning programs.
You only have to uninstall a program then check your registry and program files to see what crap is left over from legitimate programs.