RUN AD-Aware, Spybot S&D, and Hijackthis IN SAFE MODE
I suspect that some spyware that is loaded in Normal mode can unload itself and modify the registry, etc. etc. than then simply run itself in memory until shutdown. Therefore the next time you start up, it'll repeat the process such that Hijackthis would be able to see it and remove it but next time it would return. Ad-aware/Spybot would do the same thing, it may remove the registry entry but because it was resident in memory and the actual file itself wasn't detected or couldn't be removed cause it was running, it would simply load itself again the next time you turned your PC on. I had to help a friend get something off called Neededware that was like that. I would have her remove the registry stuff (O15 trusted zone as well as a XP Service (under name NDWSERV). However, it would come back the next time. No trace that I could see in the processes (easily hidden anyway) or file that was obvious.
I had her boot up in safe mode, ran all the above and it removed it. Then I had a program called CleanUp or something like that remove every stinkin temp file in %TEMP%, any suspicious file/directory in %APPDATA% and all the LOCAL DATA in her document and settings for all registered users.
Then you can run cleanmgr and delete all your system restore points in XP and also use that to remove all temp and internet cache files...
Jay
P.S. JohanD has the right idea but obviously a little work. The most important thing is to remove the file and remove it from registry second. The registry cannot start a file that doesn't exist so the first target is to kill any processes that you can confirm as being suspicious, Be careful of things in the above directory and %WINDOWS%\system32. I can't tell you how many bad files I found in there, DLLs, EXES, all suspicious!
Jay