Os resultados da pesquisa do Windows incluem apenas itens que estão em locais indexados. Você pode abrir "Opções de indexação" para ver quais locais estão incluídos. Por padrão, a pasta "Arquivos de Programas" não está incluída.
Os programas que aparecem em "Todos os aplicativos" são aqueles que têm atalhos em "C: \ ProgramData \ Microsoft \ Windows \ Menu Iniciar \ Programas \". Alguns programas podem optar por se instalar sem adicionar nada a esse menu. Mas você sempre pode criar um atalho e colocá-lo na pasta.