Primeiro de tudo, sobre o diálogo. É de uma tecnologia chamada "ClickOnce". Ele permite que criadores de software .NET ofereçam seus softwares aos usuários sem ter que criar um instalador. Quando o usuário inicia o software, ele sempre passa pelo ClickOnce para garantir que as atualizações sejam implantadas, etc.
Como a caixa de diálogo aparece quando você inicia o PC, o programa provavelmente permanece em algum local de execução automática. Como o ClickOnce detecta que o programa não está instalado no momento, ele se oferecerá para instalá-lo.
Infelizmente, com a implantação do ClickOnce, não há ações de desinstalação personalizadas. Dessa forma, as coisas fora dos locais padrão do ClickOnce permanecerão após a desinstalação. Isso também inclui a entrada de execução automática.