I would actually argue that making a good search engine with quality and responsiveness worldwide rivaling Google web search turns out to be an architecturally hard problem.

A basic web crawler is not. A semantic web crawler and associated search engine capable of mapping real human input to useful information and dealing with the heterogeneous structure of data on the web, with low millisecond latency?

Bing has been working on that problem for years now, how come they haven't caught up more with Google?

It's a much more well understood problem now than it was when google was founded and the tools and platforms available to assist are light-years beyond what was available then. Many failed search startups have shown again and again that marginally better results are not the deciding factor in using a search engine, it's what's the installed default and how trusted the brand is.

I agree. Bing seems to have mostly solved the crawling problem by now, but not the query relevancy problem.

But then again, there are also a lot of other problems Microsoft haven't been able to solve...

Making a search engine was not hard 20 years ago. But now the internet is filled with so much more crap that it actually is.