I have often used ntfstools to repair borked xp disks (recovers unbootable volumes far better than windows recovery console). I also use clamav to de-louse them - try out the excellent "insert live" cd. On many occasions, I've set up Ubuntu on the machine (multi-boot) and told the user they have that as backup if (when) windows fails again.
You wouldn't be able to easily use wine to run windows clean-up programs on a windows volume under linux, because wine emulates windows - even the C: drive is emulated (i.e. fake - it's just a hidden subdirectory). The registry you'd end up cleaning is the wine one, not the one on the disk you are trying to clean up (wine also emulates this - it's stored in a text file).
To be honest, the only way to be sure you have thoroughly de-loused an infested windows box is to wipe the hard disk and reinstall. Contemporary spy-ware is so polymorphic that it's almost impossible to definitively say you've removed every bit of mal-ware. Of course, the ultimate fix is to get rid of windows entirely and upgrade to a system with proper security and no real problems with malware. I think you know what I mean.
-cybervegan