Hmm this is weird, but it is possible Windows or some other application that boots in Safemode is booting still.
I doubt spyware would to tell the truth. It honestly just compromises every driver except what is needed.
Type this in run: msconfig
Go to the startup tab, and check in Location. It should say where the location is. Now check carefully of what you need and don't need, checking for what key you cant delete within regedit. You should be able to right click in the registry I think to check for the program location, or search for the name.
Be careful though, modifying this can damage your system, though it does have a protection feature at startup which will ask you to press okay if it works to stop the box coming up. So ignore any that same common startup, though it probably wouldn't let you stop these anyway
After you have disabled the Service or Startup function which is stopping you, restart, and then you can probably now delete the key since it won't be running
I hope this helps