I had a problem like that, turned out to be a trojan. It was renaming itself on every restart, I couldn't delete it because it was always open, and every time I removed it from the registry it reinserted itself there immediately. Adaware SE could detect it (as a series of "VX2 Objects"), but not remove it. Eventually I found I could identify it by looking in my Windows & Windows\system32 folders (I'm using XP, SP1) for files created that day. Wrote down their names (there were several), deliberately crashed the PC to prevent the rename, booted from a Windows 98 startup floppy which I had to hand, deleted the files from the DOS prompt, and finally I was rid of it. Took _ages_.
It was a vicious little [bleep] - as well as renaming itself it kept installing rogue software including "Bargain Buddy", "Recommended Hotfix", "Ad-destroyer", "Virus blaster" and several others, changing my homepage & Hosts file, and popping up adverts. Sounds like you have something similar, but it's not working properly - maybe SP2 is partially blocking it.