First thing that needs to be done is we have to reverse what ever the registry "cleaners" did. For your own peace of mine and ours, don't bother with registry cleaners. Even if there was a left over key or two in there, any slow down, which I doubt there actually is, would be measured in milliseconds, and any space they take up on the hard disk can only be measured is KB or B. That is fair trade off considering the fact the most, if not all registry cleaners delete more keys than they are supposed to. I'm willing to bet more damage has been done than you've notice so far.
That said, the thing you need to try next is a
System Restore. This should put things back as they were. If the registry cleaners were installed recently, go ahead and go back to when you installed them. This will fix the changes and uninstall the programs in one swoop.