perhaps de problem is not at the registry, the instalation log may be lost (bad instalation or it may be deleted), and the deletion registry key still may be there, but in this conditions when you try to desinstall the program this kind of messages will appear.
I think you can install again and overwrite the old instalation and then uninstall.