Hey, I had to clean up a buddy's laptop from something similar...I think you're on the right track.....
He'd downloaded every freeware/shareware virus program out there, ran them multiple times, and while we got most cleaned off, there was this one last pesky one....
What was going on was w/ this particular one, we'd run one of the clean-up programs, then reboot, and it was back. Turned out, there was another guilty file that was the cause of the problem, that the clean-up program wasn't getting, but each time the PC booted, it would generate another file that was the one showing up.
The way I found the particular file was by date; I sorted the files in the the Windows directory and located the one that was causing the problem, manually deleted it, and then it quit coming back.
Those particular ones you've isolated, I don't know about.... if you've got a boot-disk, what you could try, is to pull them out of that directory into a separate directory, see how things run, before tossing them....