Marco Arment wrote a great piece nominally about the paid App Store search rumour, and managed to deliver this searing criticism of the App Store’s search functionality in the process:
Not only is Apple searching the comparably tiny App Store, but they review every app before publishing it. With a huge staff of humans reviewing all of the input, good search should be much easier because the apps and their metadata should be relatively well-structured and regulated, and very little abuse and fraud should get through.
And yet, the App Store is still full of spam, scams, clones, and flagrant violations of Apple’s own rules, while the app-review team still capriciously nitpicks trivial and arbitrary details with the few developers who are actually trying to make good apps and represent them honestly in the Store.
I know this gets repeated ad nauseum, but it remains true: the App Store is not in good shape. A paid search placement feature dropped overtop the existing infrastructure would likely be a disaster.