But hold on... just refresh the view of HKLM\Software\Microsoft\Windows\CurrentVersion\Run and check that the entry really disappeared. If it didn't, you have some form of self-protecting malware. It could be a real rootkit, a pseudo-rootkit, or just a couple of buddy processes which look after each others' backs.
I won't go into the world of rootkits very far here, except to say that I've yet to see a single example in the flesh of what I would call a real rootkit - that is, one which runs before the OS loader and controls everything. All the ones we've had to deal with on our site are pseudo-rootkits, with the "cloaking" - intercepting API calls and returning fake information to make it look as if the malware isn't there - being done by a boot-time service.
The "buddy processes" which I mentioned might take the form of two or more standard processes, or perhaps a standard malware process plus a DLL loaded at boot (or logon) time, for example via HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Winlogon\Notify. These processes form a kind of "Whack-a-Mole" game; if you kill one, its buddy pops up another. Killing both simultaneously is hard, and killing Winlogon is generally not a good idea anyway.
Anyway, let's say that you have a file like %SystemRoot%\System32\NTOS.EXE which you can't delete or rename, or that you've used Rootkit Revealer and found a pseudo-rootkit using a driver/service file called %SystemRoot%\System32\drivers\ynhqttqd.sys which you can't even see. You have a couple of choices to get rid of them.
You could boot a different OS copy: from a CD, a memory stick, a separate hard disk partition, a separate hard disk altogether (maybe take the infected PC's disk to a different PC), or even MS-DOS 7.0 from diskette with NTFSDOS Pro, depending on how macho you are. Then go in while the system is under "general anaesthetic" and delete the offending files. You can clean up the registry entries which run the malware once you've rebooted.
If you can't do that - notably, if the PC is "far" away, defined as "further than you're prepared to walk", or if the PC can't be rebooted until midnight and you don't want to be around then - you can have Windows rename the files for you at the next reboot. To do this, we're going to use a registry value which is also used by software installation and patch operations, called PendingFileRenameOperations, which lives in the key HKLM\SYSTEM\CurrentControlSet\Control\Session Manager. This is a value whose type is REG_MULTI_SZ, which for our purposes means "a list of strings".
Each element of PendingFileRenameOperations consists of a pair of strings. The first is a full path name to a file, with a bit of magic at the start of it; the second is the name name and extension (only) for the file. Here's a sample REGINI file:
PendingFileRenameOperations = REG_MULTI_SZ \
"\??\C:\WINDOWS\System32\ntos.exe" "ntos.exe_x" \
"\??\C:\WINDOWS\System32\drivers\ynhqttqd.sys" "ynhqttqd.sys_x" \
I have no idea what the backslash and two question marks are for at the start of the full path name, but I suggest you leave them in. The backslashes at the end of each line say "we're not done yet" (there's a blank line at the end of the file to say "now we are"). If you use a different command-line tool (other than REGINI) to edit your registry, adjust the syntax appropriately.
Now, when you apply this registry change and reboot, Windows will perform the equivalent of the following good old-fashioned
REN "C:\WINDOWS\System32\ntos.exe" "ntos.exe_x"
REN "C:\WINDOWS\System32\drivers\ynhqttqd.sys" "ynhqttqd.sys_x"
Because this happens really early in the boot process, it's more or less guaranteed to work. (Only a "true" rootkit, running under the OS loader, would prevent it, I think.) About the only thing that might go wrong is if the target filename already exists, which can happen if you didn't clean up after a previous attack. So your first task whern the PC reboots is to delete the various .EXE_X and .SYS_X files.