The Windows Store thing was so terrible that I would argue the only good thing that came out of it was that it made Valve/Steam invest in Linux.

I still don't understand why the windows store search sucked so badly. It isn't like they had billions of apps. So why did it suck?

Most probably it was on purpose. MS is famous for the infighting of internal groups and how the management doesn't know how to control their divisions.