This is revisionism -- Google was far superior to any competing search engine long before Microsoft embarked on its search engine adventures. Google was hand-coding heuristics well into the Bing era. It wasn't until Amit Singhal left Google and search that they pivoted to more machine learning techniques that could use the click data effectively.
This corresponded with the beginning of Google's long decline in search quality, buffeted mostly by the fact that their on-page quality systems were extremely sophisticated at cutting out spam and SEO. The detection was far from perfect, but so many miles ahead of the competitors that their competitors kept unearthing spam that Google had long since excluded from its index but whose fossilized remains still polluted the web.
The moat that Google had was just that they were really good at search quality and PageRank was only a small part of that. In other words, no moat at all, just a better product.