We have similar issue. When uninstalling our application, if the original installation file (*.exe) was removed, renamed or moved to different folder, some of the files that were installed and belong a particular pre-requisite are not being deleted.
I also found that the key here: HKLM\SOFTWARE ...