Sorry it won’t be about Cortana but Windows Search in general.

Windows Search was great in Windows 7 - you could configure the fulltext search index through control panel and use it from the start menu. I used to index all my markdown notes and pdf documents with it. Then it started getting worse and worse with later versions of Windows. The start menu search looks comppetely detached from the index settings and, as you noticed, can’t even find installed applications. The only way to use the „old good” search is by using the search box in the explorer window when you are on the computer level. I’m still wondering what was the reason for those changes.