Out of the blue, my start -> search stopped functioning, it would just be blank.
I reinstalled Cortana using the following procedure:
Open an elevated Command Prompt window (press win + X, and then press A)
Type start powershell and press enter
Run the command (in one line):
Get-AppXPackage -Name Microsoft.Windows.Cortana | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register “$($_.InstallLocation)\AppXManifest.xml”}
After 30 seconds the problem was solved on my machine. Incredible.
Source: http://answers.microsoft.com/en-us/windows/forum/windows_10-win_cortana/cortana-not-finding-desktop-apps-when-searching/f612e995-6664-4b91-b6ae-96790e763858