Várias sugestões que podemos tentar corrigir este problema:
Método 1: Criar novo perfil de usuário
Se o novo perfil de usuário puder funcionar bem com a caixa Pesquisar e, em seguida, podemos reparar o perfil de usuário corrompido atual para correção.
Método 2: Registre os componentes do Menu Iniciar e da Cortana usando os comandos do powershell:
Get-AppXPackage -AllUsers | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}