OddTodd:
We have established that if certain registry sub-keys are present on your system where they should not normally be (namely the S-1-5-20_Classes and S-1-5-21-xxxxxxxxxx-xxxxxxxxxx-xxxxxxxxxx-xxxx_Classes registry hives) that Spybot to attempts to immunize in those keys. Patrick Kolla is now aware of that and may eventually find and fix the problem.
To overcome that problem from a Spybot immunization standpoint, just stop attempting to immunize those registry hives.
Other than that, you have not mentioned any other adverse affects the presents of those sub-keys are causing, so it may be wise to just well enough alone.
_______________
On the other hand, if you intend on continuing to try and find what software is recreating the registry keys that you claim you have deleted, there a few things that you should understand. I recommended the possibility of using Regmon because it monitors and displays Registry activity. In order to do that you must run the program while the registry is being changed, not before or after changes as you indicate that the Regmon reports you took so far represent. In other words you must run Regmon during the activity that you are interested in monitoring i.e. when the changes are occurring.
Also, if you are going to continue to use Regmon, I suggest that you the read the "Filtering Output" section in the REGMON Help File (REGMON.HLP), so that you can attempt to limit the output to just the registry keys that you are interested in. In addition, if you are correct that the registry key are being recreated at system startup, it is most likely that you will have to do a "Log Boot" to find what is doing it, so I suggest that you read the "Monitoring Boot-Time Registry Access (Windows NT/2K only)" section of the REGMON Help File also. It should be noted that when I used previous versions of Regmon, filtering did not appear work while doing a "Log Boot".
What you are looking for in the Regmon output is the program (Process) that is doing a Create Key (Request) on the sub-keys (Path) that you indicate are being recreated.
Good luck