CCleaner does not actually speed up Android phones

[Rolo]

The only issue i have with android is when you uninstall a program google pesters you to update!

Then it isn't uninstalled. This is where clearing the caches may help.

Additionally, you could update/reinstall the program and uninstall it again to see if it uninstalls properly. You could also try Titanium Backup to uninstall the app and wipe its data.

Finally, if the app is listed in settings, you could disable it; you don't get updates for disabled (or frozen, if using TiBu) apps.