Tente isso, sei que funcionará com versões mais recentes do Windows (talvez XP):
Não mexa nas chaves de registro no momento. Basta adicionar seu .exe (ou um atalho para ele) em:
C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Startup
Em seguida, vá para msconfig.exe, guia de inicialização e veja se ele é preenchido na lista de inicialização (se assim for, obviamente, verifique-o e reinicie o computador)
EDITAR:
Se você quiser usar o método de registro como você postou, em vez de adicioná-lo ao menu de inicialização:
- Crie uma entrada no registro em
HKLM\Software\Microsoft\Windows\CurrentVersion\Run
( você já fez isso ) - Navegue até
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Run
- Crie um novo valor de string e atribua um nome útil para referência.
- Defina o valor para o caminho completo (e params) do EXE que você deseja executar.
Isso deve funcionar. E se isso não acontecer, então sim, você precisará garantir que quaisquer dependências que seu exe use estejam sendo executadas antes da mão. Se você tivesse que executar o seu .exe agora com o jqs.exe desativado e ele não funcionasse, você saberá que ele precisa ser executado também quando o Windows for iniciado.