Aparentemente, a caixa de diálogo de execução verifica não apenas a variável de ambiente% path%, mas também a chave de registro "App Path" . De um artigo techrepublic sobre o diálogo de execução :
You can launch some third-party applications by typing the name of the executable file in the Open text box and clicking OK—even though the paths to these applications don’t appear in the path environment variable. The reason that this is possible is because the installation procedure for some applications adds the executable file's path to a special registry key called App Paths.
A localização relevante no registro é HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\App Paths
. Você pode adicionar seus próprios "caminhos de aplicativos" com o regedit.