Bem, o diálogo de execução! = o interpretador do comando NT.
Mas meu palpite é que ele usa o mesmo algoritmo que o ShellExecuteEx. Lembro-me de uma postagem no blog do Old New Thing que mostra como você pode imitar algumas das funcionalidades da pesquisa da caixa de diálogo Executar chamando o comando ShellExecute.
Se eu fosse a Microsoft, também não documentaria o algoritmo de pesquisa. É um detalhe de implementação.