Right-click delete of post-install is a good idea -- I'll add it =)
About the search feature, yes, I think deleting files to the recycle bin is the way to go (that way users can undo it themselves) (or, maybe giving the user options like 'delete to bin', 'backup and delete', 'delete' just as in the temp-file-remover..?)... And automatically backing up the registry entries...