The start menu is actually pretty good if you spend some time customizing it with your apps and programs. Having organized folders and groups is a "game changer" (ok not really, it's neat though) for me.

I also recommend adding all the programs to the start menu scrolling thingy. There is a folder somewhere on C: that you can put shortcuts into and they appear in the scrolling menu. Don't ever rely on the search to launch programs that aren't in that menu or setup comprehensive indexing yourself.

Or just use "everything" to search for everything. Everything is extremely fast and indexes everything (hence it's name) very quickly, and you can search with wildcards or boolean operators or my favorite regex.