1. the solution isn't always that simple and in this case it allowed the restoration of the safe-boot and perhaps reversed the registry entries for the running processes. any files previously deleted are likely to have stayed that way as they weren't in the system folders.
2. I think that system restore is so good (not) that it is permanently disabled on my system, it has severe restrictions and isn't a means of back-up.
System Restore MVP site - http://bertk.mvps.org/
There are many, many reasons why a System Restore may fail. For example, see "Why are previous restore points not working?" in the "Troubleshooting" section of this official Microsoft page:
http://www.microsoft.com/technet/prodtechnol/winxppro/plan/faqsrwxp.mspx
There's lots more on that page that's worth reading too. Note especially the sections on "Does System Restore protect personal data files?" (the short answer: no); "What should I do if System Restore does not work?"; "Why are my restore points missing or deleted?"; "Why does the System Restore Wizard lockup?"; and so on. Just a few minutes on that page ought to convince just about anyone that System Restore is not intended for heavy-duty system protection!
Run both blacklight and the panda rootkit cleaner.
Once you have done that. You might also consider proactive protection, in order to place files in the system folders and create registry entries you need permission. Prevention is much better and theoretically easier than cure.
Whilst browsing or collecting email, etc. if you get infected then the malware by default inherits the same permissions that you have for your user account. So if the user account has administrator rights, the malware has administrator rights and can reap havoc. With limited rights the malware can't put files in the system folders, create registry entries, etc. This greatly reduces the potential harm that can be done by an undetected or first day virus, etc.
Check out the link to DropMyRights (in my signature below) - Browsing the Web and Reading E-mail Safely as an Administrator. This obviously applies to those NT based OSes that have administrator settings, winNT, win2k, winXP.