Right off the bat I saw that Norton Internet Security was installed. Calling that malware isn't exactly fair but it's not far off either. Removing that helped things out but there was still obviously more wrong with the computer. Doing an in-depth scan of the computer from a *nix Live CD resulted in 1 virus, two trojans, and a handful of adware and other annoying things. All were readily removed given that the virus scan was happening outside of windows entirely.
I also took a look at their startup programs but decided that looked (amazingly enough) fairly clean. The last thing I need to do I'll do remotely -- I need to run a good defrag but since I use an SSD I haven't run a defrag in quite a while so I'm hunting around for a tool that coalesces free space then I'll run it remotely.
I must say, these were the best clients ever! While the virus scan was running I was served a wonderful salmon dinner. I think I need to include that in my rates.