Правильный подход задом наперед.
Эти ключи реестра всегда должны оставаться на целевом компьютере. Это можно сделать, пометив их компоненты как Постоянный , как вы упомянули, или установив для них пустой GUID .
После этого в одном из диалоговых окон удаления вы можете добавить флажок «Удалить настройки». Этот флажок может затем обусловить удаление пользовательского действия, которое удаляет записи реестра.