If Apple's engineers have no other ideas, I'm sure they could improve search by scraping the result of the Google (or even Bing, I suppose) search:

<terms> site:itunes.apple.com

and then using that to drive their app search results.