I am glad Ace Utilities has improved your PC's performance! It is a reputable and favorably reviewed product.
I have not found a registry utility (and I have tried many) that will remove all registry entries left by uninstalled programs. This is a potentially serious problem when uninstalling and installing firewalls and antivirus programs.
The only way to remove these leftover entries is to go into the registry with regedit or regedt32 and manually remove these orphaned entries.
A good registry utility like Registry First Aid or TweakNow will go a long way to normalizing your registry after an uninstall but the legwork is up to you.
When removing the uninstalled program's registry entries, make sure you look for the name of the company in the registry as well as the program it makes. For example, when removing Norton from the registry, look also for and remove the Symantec entries as well.
I would contact AceLogix about the scumware that you downloaded along with Ace Utilities. Always try to download from the site of the company that makes the product as there is a much better chance of a clean download then there is from downloading from a third party site.
If you got the garbage downloading Ace Utilities from a third party site e.g. TuCows, Sofotex or Download.com then I would contact that site and let them know this kind of garbage is attending downloads of Ace Utilities.
Best to you this Holiday Season,