Just to clarify. Those registry values are created by the installer or by your application?
If they are created by your application (under a key created by the installer) then those registry values are not removed on uninstall or upgrade (unless you have the "Delete (if present) on uninstall" option checked in the "Edit Registry Key" dialog).
Since user created registry keys are not known to the installer you can create a custom action (to delete them) that will be executed only on uninstall. To execute the custom action only on uninstall use following condition: (REMOVE="ALL" AND (NOT UPGRADINGPRODUCTCODE))
This approach implies that the "Delete (if present) on uninstall" option to be unchecked.
Hope this helps. Let me know if it's something that you don't understand.
Advanced Installer Team