It's called A/B testing. You serve people one of two versions of a page at random, and test which performs better. With enough data, you can be pretty damn certain that the single change caused the results. It is, in fact, hard science.
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.
It think they'll need to do some A/B/A testing to be sure.
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.
Personally I like to A/B test with new users. But I guess on an open website like Bing (instead of one with logins) you won't be able to really know if someone has visited it before.
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.