Have a look at the permissions that have been set on the RUN key within the registry - the malware may have altered the Administrator account's rights to prevent the value from being removed - try this:
To update the permissions of the registry subkey, follow these steps:
a. Click Start, click Run, type regedit, and then click OK to start
Registry Editor.
b. Locate and right-click the registry subkey:
and then click Permissions.
c. Under Group or user names, click Administrators.
d. Under Permissions for Administrators, make sure that the Allow check box
for the following entries is selected:
• Full Control
• Read
e. Click Apply, and then click OK.
f. On the File menu, click Exit to quit Registry Editor.
>>> Once you have made the permissions change, log off and back into windows to ensure your access rights have been updated, but from memory it's not required - but better to be safe than sorry.
Once you've logged back in - re-attempt to remove the dodgy value.
It it is removed, then my advice is to reboot your machine and see if there's is anything lurking on your machine that may attempt to restore the key.
Once you've rebooted and verified that the key is definitely gone, then I would spend a couple of hours scanning your PC for any more malware - trying AdWare and Spysoft Seach and Destroy for 2 good, free anti-Malware tools that you can rely on. There's pleny of others, so hunt around, but those 2 are reliable and have regularly updated definitions.