If you're seeing some but not all of your Desktop apps in the start menu search and "All Apps", there appears to be a bug where Windows 10 will only register up to 512 start menu entries, which may be the cause.
You can see how many start menu entries you currently have by running the following from within powershell
Get-StartApps | measure
You should get a count that reflects all your Modern/Metro apps plus all of the shortcuts in your start menu (one for each .lnk file). If your count is greater than 512, then a workaround is to delete unnecessary start menu entries by either uninstalling unused apps or deleting the unnecessary .lnk files from the start menu directories:
C:\ProgramData\Microsoft\Windows\Start Menu\Programs
%APPDATA%\Microsoft\Windows\Start Menu\Programs
As you delete .lnk files from those folders, Windows 10 will automatically register Start Menu links that it had previously skipped over due to the bug without you having to do anything. If you run the powershell command again it should reflect the updated count. Once you get your count down to 512, your Start Menu search and "All Apps" should no longer be missing items.
NOTE: An easy way to remove a whole bunch of unnecessary .lnk files is to delete all the links to uninstallers, since you almost always already have access to them via "Add/Remove Programs". If that is not enough, you can run WinDirStat against the two start menu folders above and sort by "items" in order to see which apps have added the most links. Lots of apps also add links to their website or documentation which you often do not need since they're just a google search away.
For me, deleting the low hanging fruit was not enough so I ended up having to move a bunch of start menu folders for rarely-used apps to a temporary (non-indexed) directory. I'm planning on moving them back once the bug is resolved. In particular, Visual Studio, SQL Server, and Microsoft's various SDKs add a TON of start menu entries.