What a disaster...No matter what you do to reset the start menu (ex: create a new user and migrate profile), once you pass the "512apps limit" it breaks the start menu anyway: Some apps will randomly disappear, you won't be able to pin anything that is outside
the start menu (ex: desktop folders), and you won't be able to pin anything from explorer via "pin to start" context menu. It will only allow to pin the apps appearing in start menu "all apps" and you can pin only from there.
Even if you reduce the number of links/apps, by moving an entire folder outside of the start menu (or deleting useless links), somehow, the start menu won't "update" : the apps/shortcuts (even moved elsewhere) will still appear there (off course with a blank
icon + unclickable because you moved/deleted them).
It has nothing to see with the search in my opinion, but it is due to the poor 512apps limitation, and how windows handles the tiledatalayer database (or the tile data server service...) : it won't reset or change once it's broken...
So, the best workaround for now, is :
1. Reduce the number of links/apps (by moving some folders, or deleting useless shortcuts)
2. Delete the Tiledatalayer/database folder, to force the start menu to "reset" : after a restart and a moment, it will "reconstruct" itself, and all apps (if less than 512) will reappear, less the store and window native apps (see step3 for that). This
folder is situated in "your user name"/appdata/local/tiledatalayer, but its a bit tricky to delete, you need do it in a few steps :
-first you need to open task manager and go down to windows processes, leave it open on the side.
-then you delete the database folder, but it will state "the file...is in use"
-so in task manager under windows processes, end "appmodel task" (click yes/ shutdown blabla... it won't shutdown in fact.)
-finally you click retry and the folder will be deleted.
Restart your computer and wait for a while, your start menu "all apps" will re-populate.
3. Re-deploy store apps, so they appear again in start menu. For that, open a PowerShell window as Administrator. Copy and paste the following line into the PowerShell window and press Enter:
Get-AppxPackage -AllUsers| Foreach {Add-AppxPackage -DisableDevelopmentMode -Register “$($_.InstallLocation)\AppXManifest.xml”}
4. All your apps are back, however all your pinned apps will be reset (the right panel will be empty) so you need to re-pin everything that you want. Personnaly I did a screen capture before, to remember what I pinned and where (use the "snipping tool" in
startmenu/windows accessories, with a delay to be able to open the start menu before the capture)
5. Optional step, backup the tiledatalayer folder. In case your start menu breaks again you'll just have to restore it (to be able to copy the folder and/or restore it, see step 2 and taskmanager trick for that)
Until it get fixed, hope it helps someone...
PS : Creating a new user profile is not a very good option and can be a real disaster, as the user SID in registry will be a different one, it means you can break all your security/permissions (if you delete the first user profile and data). So - very important-
in case you're a real kamikaze and want to do that, before deleting the original/migrated profile, go in the registry, under "HKLM/SOFTWARE/Microsoft/Windows NT/CurrentVersion/ProfileList/S-1-5-xx-xxxxxxxx-xxxxxxxxxxxxxx/" , note the last 4 digits of your
original profile (usually user SID finishes by -1001 if you did a clean install). After the migration you'll have to change the new profile SID by replacing with the original user SID. I guess there is plenty of topics explaining better than me how to migrate
a profile in a good way...imho my solution is much less dangerous.
edit: copying the tiledatalayer database from a newly created user is another option, but due to the new user SID, the file permissions would be changed (to different SID or "account unknown" if you deleted that new profile)