This may become a problem with the Android market too -- in fact, I already see it happening sometimes, when searching for particularly common application words.
I hope that Google/Android system implements some better ranking algorithm in a way that it manages to find which words are actually relevant to an application. Not sure how that'd be done, though.