A search is done when you type in the title of your new question, then click on the textarea to type the body of the question. I've found this search to be infinitely more helpful than the search bar. I believe the ask-question search just uses the titles of the questions. I don't know what the search bar uses but it usually isn't as helpful. I find myself hitting the ask question button so I could use it to do a search. Could we offer a way to use that search, as well as the search bar? Maybe an advanced search. Being able to search through the questions is an imperative feature. :D
A few recent changes in search..
Try again and see if it is more to your liking.
Not that well. Instead, you should search with google:
site:stackoverflow.com search items here
Searching with tags:
site:stackoverflow.com inurl:questions/tagged/feature-request search terms
Searching multiple tags:
site:stackoverflow.com inurl:questions/tagged/php+mysql search terms