Antes da atualização recente do Windows Creator, minha barra de pesquisa já estava com problemas e nem mesmo encontrava programas (como plano de fundo, se necessário).
Desde que a atualização da barra de pesquisa agora encontra programas como pintura eo novo Paint 3D novamente, no entanto, apenas aqueles que têm a linha "Trusted Windows-Store App" (tradução livre do alemão) abaixo deles podem ser abertos a partir da barra de pesquisa.
No exemplo com o Paint, só seria o Paint 3D que eu posso abrir sem nenhum problema.
Qualquer outro programa encontrado (neste caso, o mspaint normal) e que não tenha essa linha, não poderá ser aberto a partir da barra de pesquisa por algum motivo. Ao clicar no item, simplesmente nada acontece. A mudança de cor da animação de clique está lá, mas nada mais. A pesquisa não fecha, o programa não inicia. Isso inclui programas que eu instalei, mas também instalações padrão do Windows, como o Paint e os Serviços.
Quaisquer ideias em que o problema possa estar e como resolvê-lo são muito apreciadas!
Observação: não tenho o Cortana ativado.
Na minha máquina 15063.250 (edição Enterprise), a função de pesquisa está bem, posso pesquisar programas de área de trabalho e armazenar aplicativos. Como você disse, depois de digitar o Paint, o Paint e o Paint 3D aparecem.
Portanto,
Se não houver ajuda, tente criar uma nova conta de administrador para testar novamente.