Are we all forgetting why Google has the brand it does? There may be minor algorithmic differences between search engines now, but in 2000 Google's results completely crushed those of other SEs.

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.