The complete solution. It worked for me.
If you use Bootmagic, start the infected partition. Open the BootMagic config app and set the infected partition as default then uncheck "BotoMagic enabled".
Put your Windows (XP) CD into your CD-rom. Restart.
Right after starting up, press F8.
Choose to start up from IDE CD-ROM.
You'll get a screen with install windows, just wait a few minutes.
Then, when it's finish loading, press R to start the repair mode.
Select C:\WINDOWS
Now comes the tricky part.
Type CHDIR C:\WINDOWS\SYSTEM32\SERVICES
The line that first said C:\WINDOWS will change to C:\WINDOWSSYSTEM32SERVICES
Type DIR
You'll get 2 files saying . and .. and one or more saying {05A2C6C0-187D-44EC-AB5A-D2DFFBC90D3C}, that's what one of mine said, yours may be different.
Now type CHDIR and copy the line with the long name
The C:\WINDOWS\SYSTEM32\SERVICES will change to C:\WINDOWS:\SYSTEM32:\SERVICES\longfilename
Now type DIR once more.
And type DEL and copy the filenames in the list one by one. This will delete them, something that would be impossible in Safe Mode.
When finished, type CHDIR C:\WINDOWS\SYSTEM32\SERVICES
Type RMDIR and the long filename again to remove it.
Repeat the process for the other files.
Type EXIT now to reboot as you usually would do, and then, you should be free of it. Then reactivate Bootmagic.
Do not use IE, because it's a paradise for stealth software, and so on. Just use it when needed. Use the free Mozilla Firefox
www.mozilla.orgYou should have Norton Antivirus, AdAware or something like that.