It used to be that once upon a time the System Restore folders were well enough protected that nothing wrote to them. As time went on malware writers found a way to do this, and now it is common place that the system restore is infected to give the malware a good chance to repropogate itself.
Because malware has given itself the ability to write to the system restore points, alot of antimalware applications have given themselves the ability to access and delete infections from the restore files. This requires a reboot, so before the operating system fully loads and tries to protect the restore points, the antimalware apps clean the junk.
When ever I perform a malware disinfection, for a second AV opinion I disable my antivirus and other realtime protection and run an online scan. If / when the scan comes back clean the first thing I do is purge the restore points and create a new clean one.
I used to use spybot and adaware, but now I have traded them for Malwarebytes' Anti-Malware and SUPERAntiSpyware. In my opinion they have a much better detection and removal rate. The downside is the free versions don't run resident (I actually prefer this as it frees up system resources, and I update run my scans periodically).
Even if it is just for curiosity sake, I would download the 2 apps and run them, I'm sure you will be surprised the junk they can detect. If you do this make sure you include all drives and if you can, any removable media in the scans.
http://www.malwarebytes.org/mbam.php
http://www.superantispyware.com/