Maybe the machine is infected and has neutralized the AV. It wouldn't happen to have Java on it? There have been a couple of very successful exploits against Java. This weeks most recent release fixes them assuming you manually download and install it (as the updater is busted it seems).
If you are not sure give the Standalone System Sweeper a try. http://connect.microsoft.com/systemsweeper
Use a known clean machine to run it and create a bootable USB or CD to use to boot the suspect machine and possibly clean.
