Если вы создадите установщик для своего приложения с помощью проекта установщика Visual Studio, вы получите деинсталлятор вместе с ним. Это работает так же с установщиком NullSoft и WiX. Это работает так: файл MSI (файл установщика) - это не исполняемый файл, а файл базы данных, упакованный вместе с файлами приложения, и он сообщает окнам, куда поместить файлы. Когда Windows устанавливает ваше приложение, оно регистрирует то, что делает, и поэтому, когда оно удаляет, оно отменяет то, что находится в журнале. На самом деле все намного сложнее, но в принципе так оно и есть.
NullSoft и WiX намного лучше базового проекта установки Visual Studio, который сложен и очень загадочен, поэтому попробуйте использовать один из них, если можете.