Wow... you've got one of those really intricate self-preserving spyware programs. Have you run a simple integrity check of your system files? It might have replaced a basic system file with a different copy including a re-installer for itself. Under Win 9x you run the sysinfo utility and there's an option to run the system file checker under the tools menu. Dunno what the equivalent is for 2k/XP.
I think you really need to get Spybot S&D. It's pretty good at destroying nasties like this.
http://www.safer-networking.org/