CCleaner does NOT check for what's called empty keys which is what needs to be deleted. I'm not home at a minute but when I get home I will post a link of the registy cleaner I use it will fix your problem. I will post it tommorow.
Glad I can help-Supreme Kotor
Edit: So the program I personally use is called Registry Easy. It is free but you may only clean 30 registry entires each scan with the free version this is not a big deal it just may require a little patience. You may allow it to clean your entire registry but all you should need for this probablem is:
1) Emplty registry Keys
2) Shared DLL's section
3) And because it sounds like your uninstall had issues just throw in Uninstall entires.
*Remmber if you have it clean the user setting and system settings any personal changes (Ex: Hotkeys, brightness, backgrounds) will be "forgotten" by the computer.*
This should fix your problem if not post here and we can try another fix