The problem of App Search is that app search is a small fragment of the overall search market, and that most searches on the web are for one data point (e.g. search for Chez Panisse restaurant in berkeley or weather in Cupertino). If you have a frequent use case (Yelp, Uber) or an infrequent but very important one (Opentable, Trulia), you are going to download the app. But otherwise? You are going to keep searching on Google, not on the AppStore or on Quixey.

The only way around that would be to index the content of the web content of the app themselves. It would be great, but only Apple can really do that right now... and they are not even trying to. That would be in my mind the only way to make app discovery a reality.

Now for productivity apps/games, they correspond to highly used or niche applications...but are people really looking for them? In the early days of PC games, people were reading review magazines and going to their local Best Buy to discover the best games, and the app store is no exception. I don't see how Quixey would help me there since most of the best games I have played on the iPhone are impossible to describe and you would never have searched for them if Apple had not showed them in front of you...