Do you have Spybot S&D? The Immunize feature and a full scan would probably help since not onyl will it scan for stuff an AV product sometimes misses (Not as much of an issue today with AV companies also giving out Spyware and cookie detection options, but still a thought) and the Immunize will also go to the hosts file and make it a bit more locked down, and of course it locks down IE, Firefox, and Opera so that this kind of thing is harder to get infected with if it's an infection.

You could also have them use Opera with Spybot so that they're not as likely to infect themselves. If they complain about your efforts, tell a boss what they did and how they're a huge risk to the network, and that you could clean it up, that way you've got the CYA principles down.

If all else fails, all users appreciate a disk format