Hi Downloaded! I've not been around so I've not welcomed you to the forum yet so welcome!
From my experience, System Restore rarely (if ever) restores deleted files. What it does is usually restore to earlier settings, which could possibly create even more conflicts even certain key files are already gone.
If the programs that you've uninstalled reappear, try to uninstall them again (usually works for me). Or you can try using the Microsoft Uninstaller cleanup utility. I've downloaded it once and it works pretty good.
I've found a link to it, but I've not re-downloaded this to test if it's the right one so if it's not just tell me and I'll go google hunting a bit more.
Description of the Windows Installer CleanUp Utility
Also, I'm not sure about your current computer set-up but what I usually do if I've done a major screw up is I'd do a clean format. I've my laptop partitioned in such a way that reformatting comes easily.
If your desktop holds most of your vital files, doing a complete reformat of your laptop would be in my opinion the best way to go. That way you can start with a clean slate and when you need to optimize your OS the DAL guys here can help you do so safely.
Out of curiosity though, are you running XP, Vista or Win7?