I managed to fix the issue and I think this answer can be relevant for some of the problems reported in semi-related questions. I want to tell you everything I know with as many details as possible so if my fix is not working you can come up with something reading this. That's why I wrote tl;dr section.
re-enable UAC / EnableLUA. Mark
%ProgramData% folder as not readonly, verify permissions, also try Windows 10 Search can't find ANY applications. Even calculator
My exact steps
- Installed Windows (upgraded from Windows 8.1 with total purge of system drive)
- Performed my initial setup ritual* (this was the cause - see below)
- Installed some new apps
- Noticed search is not working properly
- Tried rebuilding the index to no avail
- Deleted all files in Windows Search directory (made things worse)
- Tried rebuilding the search index once again (no effect at all)
- Run windows search troubleshooting
And this was the first I got some valuable feedback:
Incorrect permissions on Windows Search directories - (red cross) Not fixed.
I verified permissions and folder attributes of the aforementioned folder and everytihng seemed to be OK. So I thought "ah, what the hell" and enabled UAC, rebooted Windows and was shocked by start menu search correclty without even rebuilding index etc.
My initial setup includes many steps like installing web browser, email client, VPN etc. and
Disabling UAC globally (EnableLUA->0 method)
Why? I am not in danger, Skyler. I AM THE DANGER!
I fixed Windows, made workarounds for Windows and .NET bugs, hacked windows kernel etc. so I find UAC very, very, very annoying because I am not your normal, everyday user. I don't need to be protected by system, it is the other way around. I am aware why metro apps won't work in this mode and I understand this totally. As far as I know many people disable UAC like that
Very important thing is I did this in Windows 8.1 and didn't experience such problems
After looking at some other questions here, at Super User I found one asking about indexing on SSD in Windows 8, I remembered Windows 10 Control Panel Search and Indexing options and launched Windows 8 to see if I can give a step by step instructions how to resolve his issue using these settings. But turns out this is new in Windows 10 (I never really looked at all elements of Control Panel, I rather used mmc). After some searching (oh, irony!) I found out that the new indexing mechanism in Windows 10 doesn't work with UAC disabled, until this is fixed I have to update the index after installing new apps by enabling and re-disabling UAC.
If I have time I will try to come up with workaround if this will not be fixed by Microsoft.