Searches are usually slow, and even freezes the app, when number of notes are very large. It is frustrating and keeps the user waiting. I am using Evernote as a news feed reader. If I want to fire a search, I would most of the time require results say top 10 or top 20 from the most recently created/updated notes.
This creates a case for a feature requirement, where search process suspends (and not continue searching exhaustively), after displaying such specified number of results, with a "More.." button at the end. If the user wishes, he can continue to get more results, by clicking the button.
It will save time and resources, and make the app responsive.