I've noticed this as well. It's not that it freezes, but it can just take a little while to complete the search. I wonder if it might be partly related to what Google Search is set to search. You'll notice that if you open Search and then tap the menu button and select Settings/Phone search, you can select where you want Google Search to look when you enter a search item. If you have a lot of things checked, it might bog down a search, since Google Search has to look at all of those locations as well as on the web. I just tried unchecking everything except Browser, and it seemed like it was a little faster, but it might be my imagination. Obviously, if it's important for you to use the Search button to globally search your phone as well as the web, then it's not worth editing these settings.
Facebook
Twitter
Instagram