(Edit: This answer mostly relates to Windows 10 prior to Version 1511.)
The Windows 10 Start menu has several known bugs.
You might have run against the particularly noxious bug
limiting the total number of entries to 512.
That's not 512 applications, by the way - that's 512 items in total, including apps, folders, files and shortcuts.
(EDIT: starting with Version 1511 Microsoft has significantly increased this limit.)
The best solution, in my opinion, is not to fight against these bugs,
since you really have no other option than wait for a fix from Microsoft.
Instead, until Microsoft gets its act together, replace its Start menu
with a third-party one. The top contenders are :
Otherwise, here is a list of workarounds for the Microsoft one :
- Rebuild the search index by going to Control Panel / Indexing Options / Advanced and using the Rebuild button.
- Reset the Start menu layout by opening an elevated command prompt,
exit Explorer, delete the Start menu database at
%LocalAppData%\Microsoft\Windows\appsFolder.menu.itemdata-ms
and run Explorer again. (EDIT: this file no longer exists in newer versions of Windows 10.)
- Ensure your Windows 10 Start Menu does not exceed 512 items by reducing the
number of indexed locations
- Reinstall all applications, by entering in Powershell as Administrator
Get-AppXPackage -AllUsers | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}
- Try a new user account, since your profile might be damaged
Even if one of the workarounds works for you, the bug can hit again at any time.
The only lasting solution is to use a more stable Start menu replacement.