[DartVanya]

Таки решил проблему, создал пользователя, а на нем программы искались, стал искать в сторону AppData конкретного пользователя, в итоге решил так.
Закрыть SearchUI.exe, explorer.exe и снести чем-нибудь:

C:\Users\[имя_пользователя]\AppData\Local\Packages\Microsoft.Windows.Cortana_cw5n1h2txyewy

Не знаю, наверно может имя в конце отличаться.
Затем выполнить в powershell c правами администратора:

Код:

Get-AppXPackage -Name Microsoft.Windows.Cortana | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}

После чего у меня в поиске стали искаться программы и все заработало, закрываю.