Well, the best thing you can do when uninstalling software is to use Revo Uninstaller
. It scans the hard drive and registry for leftover files and entries (some programs don't clean up after themselves, as you have also shown). I always use it when uninstalling software, with excellent results.
But, since you've already uninstalled these programs and are simply left with the clutter left behind, there are a few options:
Option 1: Clean install of Windows 7. I know you said you don't want to do this, but it is an option, nonetheless.
Option 2: Reinstall all those old programs, then uninstall them using Revo. I know it seems counter intuitive to do this, but the thing is, Revo can't see those program leftovers right now. Once the programs have been uninstalled, their entries as installed programs are gone, and you're just left with the leftovers. Revo was made to remove the leftovers immediately following uninstallation (everything is done through Revo, so it keeps track of what's going on). So, theoretically, if you reinstalled those programs, Revo would be able to fully remove them this time.
Option 3: Search out the clutter manually and delete what you find.
That's about it, as far as my knowledge goes.
The biggest problem with program leftovers are security programs (firewall, antivirus, etc...). For example, if you don't use the Norton Removal Tool, Norton will leave parts of the program all over your computer when you uninstall it. This can come back later to haunt you (I've seen it happen many times). There isn't really a danger/risk with other common programs like video players, word processors, games, etc...besides the obvious loss of hard drive space.