The problem with automatic registry cleaners is they tend to find only those entries which are determined to be "safe" for removal. That doesn't mean they will detect ALL "orphaned" entries and it doesn't mean the ones they DO detect will actually be safe to remove. As you know, even the "good" registry cleaners can occasionally delete the wrong thing.
That's why many programs, such as Norton and McAfee, have manual removal instructions which include registry key deletion. Because I've uninstalled so many versions of McAfee many times, I've accumulated most of the manual uninstall instructions for most McAfee Virus Scan products. Some programs such as Norton and McAfee actually have a special registry removal "tool" which deletes most of the registry remnants. In my opinion, although I use registry cleaners on occasion, if you really want to clean out the junk of a specific program, you'll want to research the specific program and find it's manual uninstall instructions. It's safer and more thorough.
AOL is really tough to clean out and even AOL doesn't provide great manual clean up instructions but if you check the net or these forums, you'll find quite a few posts about it. AOL is a different beast entirely.
Hope this helps.