The brand is it. And branding doesn't sink or swim based on name alone, but it isn't a trivial factor.
And the reason I brought up brand is that Microsoft has to build one now. And for that task, the letters matter.
Quality of results (and speed) matters most. Brand starts to matter when a product or service becomes a commodity and competitors need to differentiate themselves, which is essentially the situation we find ourselves in now with search. But to say that brand is all that matters is a little simplistic. If Microsoft has truly created a better search product in terms of results and/or speed then brand matters much much less.
But I do agree that there is a perception that Microsoft doesn't know how to innovate in search and on the web generally, so the decision to leave the Microsoft name off of Bing makes complete sense.
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.
It's more like the other 99.999%.