I am not an internet god, but I do manage a small network of devices whose users occasionally get into situations like yours. What I have found very helpful is to download and run two free programs regularly. We run Ad-Aware and Spybot, both available for free at download.com

Each one does a pretty good job of finding the pollution on a system, and when used back to back they seem to clean almost everything.

I'm sure there are more god-like folks here who can help you more; hope this also helps.