The only 3rd party app I have that I've run since actually looking at System Restore is Perfect Disk which is a disk defragger that you're probably familiar with. Before I was thinking if a 3rd party app was interfering in some way, but I couldn't think of what it might be save Perfect Disk or a few Registry cleaners that I use. Speaking of which, I use: TuneUp Utilities 2007's reg cleaner and the the free reg cleaner called Wise Registry Cleaner and finally TweakNow's Powerpack 2006's reg cleaner.
I don't think it's the reg cleaners because I remember previously that I looked at System Restore prior to running the reg cleaners and my restore points were still there after I ran them and even after rebooting. I didn't look before or after I ran Perfect Disk though, so maybe that's the culprit. The thing is, I was using Diskeeper 11 and I had the same problems, so either Diskeeper and Perfect Disk are erasing restore points or it's another problem.