You’ll need to browse a little here in forums as recently other threads relate that virus/rootkits are doing this behavior: deleting exe files.
Some users could manage it with antirootkit tools. Check http://www.antirootkit.com/software/index.htm
Specially, Panda and F-Secure ones.
S*it… a very bad one…
Did you try booting in Safe Mode and running F-Secure?
Did you try any other on-line scanning?
Do you have another computer to plug this HDD and scan it from there?