On the "processes" tab in taskmanager, do you see "winlogon.exe" and "services.exe"? Just trying to verify that windows has completed the logon process...
I'm thinking Bill is onto something with his last post. Most spyware removers do have an "undo" function.
If you deleted the keys manually, you may be able to recover the missing registry keys with this:
http://www.kellys-korner-xp.com/xp_tweaks2.htm#fix
In the Utilities for XP box, use the drop-down menu and select "recover and restore deleted files".
This is another "longshot", but it may provide a solution...