There are obviously a couple of caveats. First, you need to run the two tests in parallel as you allude to, and second the separation between the samples needs to be completely random. I would assume that Microsoft can keep these caveats in mind.
Switch back to the original shade only for those that experienced the new shade. Maybe they'll see another multi-million dollar increase? That way you could further prove that it's indeed the color that made the difference and not simply the fact that the page was changed at all.
Added:
The Hawthorne effect is a form of reactivity whereby subjects improve an aspect of their behavior being experimentally measured simply in response to the fact that they are being studied, not in response to any particular experimental manipulation.
Suppose you ran an A/B test like you say.
User 1 goes to website, it's site A. Dislikes it. Nothing happens.
User 2 goes to website, it's site B. Loves it. Tells friends.
Now how do you track that 'virality' element? How do you know if User 1 was the cause of increase traffic, or user 2?
How do you know if I tell my friend "Hey checkout bing it has this awesome blue color", and how do you know if I was an A user or a B user?
I think there's just too many untrackable elements in a case like this.
And in any case, the story still sounds like there was no A/B testing involved. Just "we changed a color", and later, stuff happened.
Or their A/B tester implemented as a genetic algorithm evolved the colors towards those used by Google because that increases their chances for survival :-)
You can't change a color, see things increase, and claim it's all down to a change of color. Also as bing "increased", Live "decreased". Has Bing been successful?
It makes for a fun PR story, but it's complete BS.
Whatever happened to science? How much money did Live search make? How much is Bing making? Have they been able to add any traffic?
Some hard data would be interesting.
One point to note is that they essentially copied the colors straight from Google.