Uma primeira foram é TECLA_WINDOWS + R (executar), então abrirá uma tela para execução de um comando. Digite:
shell:startup
Após isso basta copiar o .exe para a pasta que foi aberta e, assim, ele vai executar ao iniciar o windows.
=>bom, depois verifique. Isso deve resolver para a maioria dos casos.
Para verificar, abra o Gerenciador de Tarefas e clique na aba Inicializar (tem que aparecer na lista). Se não apareceu, tente resetar o computador e verificar novamente.
Se isso ainda não resolveu tente checar se existe alguma outra pasta que não seja apenas do usuário corrente.
TECLA_WINDOWS + R (executar), então abrirá uma tela para execução de um comando. Digite:
shell:common startup
IMPORTANTE TAMBÉM: veja se o executável está marcado para executar como administrador.