I fully agree: The start menu was never a good idea, we just used it. As soon as you start installing and removing things, it quickly became cumbersome. Windows XP (iirc?) introduced weird ideas of how to cope with the chaos in that evergrowing, 3-4 level deep list of things you might or might not want to start: The 'personalization' feature that kind of randomly hid most of your menu. The hacks to order the menu (which never really worked reliably).
So the options today are fine, for my usecase, and I'm hard pressed to accept that the old solution was better in general.
- Pin programs to the taskbar
- Use shortcuts for common/important stuff (Win+i, Win+x, Win+w, Win+f are the ones I need)
- Use the type to complete thing otherwise
Most users I know moved to that workflow anyway, before Windows 8 (the start menu entry on previous Windows versions. Spotlight or maybe QuickSilver before that on OS X. Unity / Gnome Shell on Linux).
In my opinion the start menu needed constant micro-management and was a hassle.
(Disclaimer: I'm not happy with the ui formerly known as Metro, but I do like the 'type to launch' approach a lot)