Earlier quoted context omitted.
How can a site this large get away with such a basic functionality not working as any of their users would want for such a long time? Did it ever work? I think I've noticed it not working like 5 or 6 years ago when I was shopping for shoes, if not earlier than that. Keep in mind that even without Zappos, they're in the business of selling shoes, too, and have ran some crazy promotions around shoes, too.
Have you ever tried searching for apps on the Google/Android Play store? It's a complete disaster if you're trying to find something specific that's not in the top 20 apps. Given that Search is Google's specialty my personal conclusion is that search is fundamentally broken on the Play Store on purpose.
So I guess google just heavily filters, limits and shuffles apps so they are somewhat evenly distributed but it does look to end users like a buggy search that can't decide if it has the app or not returning different results for the same query.