That perception only exists among the sort of people who read this site. The other 99% of the populace doesn't think that deeply about it, and even if they did, they have a much more favorable opinion of Microsoft.

They started going to Google for whatever reason and stuck there because for many years it was light years ahead of the rest in terms of quality. Now it's going to take a much better search engine to top them. And if Microsoft made that engine, they could just leave it at live.com and grow (and at least it'd have the old 8% market share to start with). And if they don't, they can change the name every week and totally disavow any involvement but it still won't matter.