When I uninstalled SpyBot S&D Beta, I disabled all it's services beforehand. Immediately after that, without restarting Windows, I was able to uninstall via Add/Remove Programs.
There were a few folder/files in it's install folder, which I deleted via Windows Explorer. I haven't yet bothered to check the Registry, as I will install the pre-release version, if there is a method to permanently disable SpyBot S&D services from running. On this WinXP Pro machine, they all restarted on Windows Restart after being disabled.