It gets a lot better when you turn of web searches for the start menu search. Perhaps some people like having a single place to search for applications to run, documents on their PC, and things on the web. But I'm not one of them, and it slows down the search as well.