I'm running build 10240 and RTM and it works on both machines. Have you applied the latest updates and done a re-boot.
I'm very happy with it now. Here's what Windows up (that's all I had to type --) shows - direct into the settings.
When I had typed win it was showing WINAMP which I have installed - so I just kept typing until windows update showed.
IMO works perfectly and really easy.
I don't know if activation (or lack of) causes any problems as you can't personalise your machine if not activated - I used the "bog standard" default settings anyway -- both these machines though are activated.
@lolcocks: in Win7 this was not dependent on registry settings. Start menu search simply looked what you typed up in places like "%appdata%\Microsoft\Windows\Start Menu" - and what I and you are searching for is definitely stored in there!
@fracking4oil: no cortana active. Cortana needs an MS account which I do not want to have. Could you please test if you can still search for your desktop apps if you temporarily disable Cortana?
@jimbo45: I'm running the final build, I got it via MS' Media Creation Tool x64. I'm running the latest updates (30.07. 12:03 UTC+1) with the machine restarted. Windows 10 says it's activated (though I don't remember to have entered my product key ... remember this is a clean install and not an upgrade install from a running Win7.)
@all: I also upgraded my Tablet OS from 8.1 to 10 via Media Creation Tool x86. Start menu search works there as expected with no Cortana active. On the tablet I did an upgrade keeping all my files, settings and apps.
I don't know why it works on my table and why it does not work on my desktop computer. Still no luck with google finding other users affected by this. Let's hope more users chime in here and describe in detail what they did ending up with this bug so we can maybe find a pattern causing it.
It seems that the indexer is quite slow when rebuilding the database even using an SSD. After hours, it works here.
If problems persist, it may be a good idea to re-index: Control panel->indexing->advanced->rebuild
Control panel->indexing: Check in the upper part of the window if indexing is still going on or if it's done. If it's still going on and the number of indexed elements keeps rising every 10 seconds or so, you simply have to wait. If it's done, there should be a statement like "Finished indexing".
Also, check what folders get indexed. First, activate the option "show hidden files and folders" by opening the Explorer, then check View->Hidden Elements. Now open Control panel->indexing->change/customize (again, I don't know the exact name of the button) and then check if the following folders are checked for indexing: C:\ProgramData\Microsoft\Windows\Startmenu C:\Users