Dude, when something is this bad, DO THE DAMN FORMAT.

There is like no way you're going to be sure of getting rid of everything unless you do the reformat.

Back up what they guy wants to keep, and format that HD, and reinstall. Then, install AVG and a firewall. Then update the thing, then update AVG, then the firewall. Do a scan of everything, then install Ad Aware, update, run, and then, charge this guy an extra stupidity tax.

Hopefully the people reading realise THIS time I say this **** to get you to laugh and not be stressed out over it. Anyway, I really don't think you're going to even WANT to try and clean it. You'd need Holy Water for that thing.