Via Custom Actions : As you can include a console application (that you will add to your program directory) that you create to remove this registry key when you perform Uninstall.
First of all, add your Console App Executable to your program files.
Select "Custom Action Editor "
then right click on Uninstall Action and select add,
then select your console application that all it does is to remove your key.