Phil has already answered, but maybe I can add that you can use (REMOVE="ALL" AND NOT UPGRADINGPRODUCTCODE) for the custom action to be executed during uninstallation. Then just set the registry component permanent (HKCU registry data shouldn't really be uninstalled either - a matter of some debate though). This still won't fix the HKCU data for users who are not logged on at the time of the uninstall though. This is a much more involved task, probably possible to do with ActiveSetup.
Adding NOT UPGRADINGPRODUCTCODE ensures uninstalls performed as part of major upgrades do not update the registry since the product is then due to be reinstalled. Shouldn't be necessary for your case, but ensures the custom action doesn't run unnecessarily.
I would suggest scheduling the custom action right before InstallFinalize in the InstallExecuteSequence. I haven't tested this location, but it is then one of the last actions to run during the uninstall, and should have the desired effect.
See the condition lists for detecting different installation modes at the bottom of this thread.