Some of the newer viruses or spyware have coded to prevent their easy removal. Sounds like you have one maybe.
Only hope sounds like a DOS scan to see if you can pick the offending files up, using a DOS boot disk made by a leading anti-virus app, or booting with a AV CD-ROM. Not guaranteed to work though, even so.
Do you have a CD copy of, say, Norton AV that you can run from the CD (NOT from within windows!). If you have, boot with that CD and try to do a full scan. Might not work if it's an older CD (virus definitions may be too old), but it's worth a shot.
Otherwise, only other option is to reformat, I'm afraid.
Sorry to say, but some of these newer klez-type viruses are awful hard to get rid of.
Cheers
Mick