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.
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.