Create a software resource, including the removal script as part of the package, and then write an uninstall command line that runs the script you included in the package. Create a detection rule that detects when registry entries are present. Save the software resource. Create a managed software delivery policy for the software resource and assign it to all computers. It will execute on all computers and, if the registry entries are found (detection rule = true), the uninstall command line will run, running the script and removing the registry entries.
Be sure to test and pilot before assigning to all computers in production to ensure you have the expected behavior. Does this answer your question?