Contrary to popular belief, it is actually a very bad practice to use any of these third-party "cleaner" tools. The chance of them breaking something is far higher than the chance of them actually helping, although they are mostly just snake oil. For instance, Windows has a built-in tool to clean up old temp files, and it's had it for a very long time. Why you would use CCleaner for this is beyond me. If there's anything CCleaner deletes that Windows doesn't, there's probably a reason for that, and I'm inclined to believe Microsoft knows more about their own OS than the CCleaner devs (please hit cancel on any dumb Microsoft jokes you're about to post). I've literally seen people break their computer doing exactly the thing you described, because they didn't realize those old "temp" files were actually the uninstallers for applications that were still installed. You ever try to uninstall something through Control Panel only to get a "cannot find file" error? That happens because someone or something deleted some files they weren't supposed to.

And /u/EvilC0leslaw is right. The registry doesn't need to be cleaned because the registry can't get "dirty." It's just a hierarchical config file store. Firefox puts its registry keys under HKLM\SOFTWARE\Mozilla. It makes no difference to Firefox if there's a bunch of unnecessary keys under HKLM\Software\App You No Longer Use.

That's fine. It's moreso the core "registry cleaning" function which is pretty much useless, and in some cases could cause issues. Orphaned registry keys really aren't going to cause a problem for a system in the vast majority of cases.