Duplique um atalho da pasta Menu Iniciar que já pode ser encontrado nos resultados da pesquisa. Use a janela Propriedades da cópia para alterar seu nome, caminho e diretório Iniciar em para o executável desejado. O programa começará rapidamente a aparecer nos resultados da pesquisa.
Isso funcionou para mim na pasta do menu Iniciar por usuário e na pasta do sistema. Curiosamente, criar um novo atalho para o mesmo programa (sem a duplicação) no mesmo lugar depois de fazer o acima, faz com que os resultados da pesquisa usem o nome do novo atalho.