Remove uninstalled apps that show up on Windows Search

You could try these reset ideas- whether they will help I can't possibly say.
How to reset the Start menu layout in Windows 10 - Winaero
How to backup or reset the start menu in Windows 10 - gHacks Tech News
How to fix your Windows 10 start menu (reset tile database) - Spiceworks

Note some of these seem more directed at tiles.

Sorry, no more ideas. P.S. I don't use Win10's start menu... look what it does to my nested menus with sub-sub folders..


- those are all in the folders the relevant program created when it was installed. And you've probably guessed- I use Classic Shell start menu to avoid all these snags.

See reset ideas in amended post above- just check carefully if that seems appropriate.

If you've rebuilt the search index, that leaves the possibility there's some sort of other cache, I suppose.

If you use search from Classic Shell (which also can use the Windows search database), does that find any of them?

Another approach might be to try to reset Cortana related data.
Clear Personal Data and Information from Cortana Windows 10 Performance Maintenance Tutorials
Perhaps option 5 - it's just a guess though.

There's an interesting hint here:
Force a rebuild of the start menu program index/database in Windows 10 - Super User

Originally MS set a silly limit of 512 items that can be indexed on the start menu. That was raised to 2048.

The fact that there is a limit also may suggest a separate database.

@Phaellow - I know you said this affects all users. Now if the database is built per user, and the shortcuts do not exist in the start menu folders, what do you think would happen if you now created a new user?