Windows 10 search doesn't show new programs

Question

I have what appears to be a common problem with Windows 10.

There is a fresh installation of Windows 10 Home 10.0.15063 on my computer. However, the Cortana search does not find programs that are installed by a user. It works just fine with system apps but doesn't show applications like Word, Steam, etc...

As it seems that this problem is actually occurring quite often, there are several solutions online for it.

What I tried:

• Checked if the Start Menu is selected for indexing (yes, it is).
• Rebuilt the search index.
• Ran the Troubleshooting for Search and Indexing. That revealed Incorrect Permissions on Windows Search Directories, but I double checked and the permissions for C:/ProgramData/Microsoft/Search are in fact correct.
• Reinstalled Cortana using PowerShell
• Ran sfc /scannowas well as dism /online /cleanup-image /restorehealth

All of that without any success. I am slowly but surely running out of options to try out.

Is there anything I missed out other than a Reset?

Thank you for your answers.