One of the few good things that I will grudgingly admit Windows Vista had was the search functionality in the start menu. This got even better in Windows 7.
Every since, I have barely looked at the start menu, if at all. All I do is press the Windows key, start typing the program I need to launch and Enter.
This works exactly the same in Linux, so I never bothered looking at how to customize this as I never look at it for more than two seconds. And when I notice that I use something often enough, I create a keyboard shortcut for it.