After using Windows 10 for a while I grew similarly fed up. I found OpenShell [1] to be a very faithful replication of the old start menu I'm used to from XP and before.

1: https://github.com/Open-Shell/Open-Shell-Menu

I’m still stunned at how bad Windows search is. They’ve been trying to get this right since they begun development of Windows Vista nearly 20 years ago.

Meanwhile in OS X land, their 16-year-old search implementation has always been so good that in a lot of cases, the file manager isn’t necessary to find even the most obscure and poorly organized documents.

This is something that is really puzzling to me, how such a basic and useful feature can be broken for years. It's annoying me since the release of Windows 8.

Keyboard Launchers like Keypirinha (also used Launchy back in the days) are my current workaround. They can index what the start menu should be indexing and do it right. I also keep my own (synced) folder of shortcuts that I add to the indexing.

Pin to the star menu?