AdAge in a recent article publishes information that Microsoft is branding a new search engine Bing. Upcoming campaign budjet is estimated to be around 80-100 million dollars, and JWT as the agency who's doing the work.
As an interesting side note, Microsoft's own search front end statistics show that 42% of searches require refinement, and 25% of clicks are the back button. I wonder if Google has similar figures?