A pesquisa do Windows é integrada através do Menu Iniciar, portanto, quando você vê arquivos que são executáveis, isso significa que a pesquisa do Windows não está mostrando a entrada do menu Iniciar, mas o arquivo real.
Normalmente, um link do menu Iniciar para um executável substitui o nome do executável, portanto, a pesquisa do menu Iniciar mostrará apenas um e não ambos. Quando a entrada do menu Iniciar estiver faltando, ela começará a mostrar o nome do .exe e não o nome do link do menu Iniciar.
Portanto, o problema continua sendo que os itens estão faltando no menu Iniciar. Você fez alguma alteração no computador recentemente? Caso contrário, esse tipo de comportamento grita "vírus", "software torrentado" ou "outra pessoa está mexendo com meu computador". Você usa uma senha na máquina para que filhos / esposa / amigos / colegas de trabalho não causem problemas? O software é autêntico, portanto, as atualizações automáticas não causam problemas?
Os links estão ocultos ou marcados como sistema em C: \ ProgramData \ Microsoft \ Windows \ Menu Iniciar \ Programas \?
Desculpe pelas perguntas, vou editá-las se você editar sua pergunta para incluir essas informações e tentarei deixar uma resposta melhor que eu puder aqui.