I have got lots of files in AppData/Local pertaining to previously uninstalled applications.
A useful feature would be for CCleaner to keep a registry of known applications and the directories that get created in AppData/Local.
Then you scan to check to see if the application is installed and offer to remove the files if it is no longer installed.
You would have to be careful in case people have installed portable applications that are writing there so I would imagine that it wouldn't be an automatic clean but a list to say this dir corresponds to this application. If you know you no longer have it then tick to remove.
You could start with some fairly common applications then provide a feedback form that let the community say that this dir corresponds with this application.
After verification, the application database could be updated making the application even better!