Last week, Clickz revealed a research paper by Ostrovsky et al from October 2005, showing that advertisers overpay, using Google's auction method for AdWords (see this PDF for AdSense). Ostrovsky et al claim that Google wrongly states that it uses the Vickrey-Clarke-Groves mechanism (VCG). Instead, Google uses a generalized second price auction (GSP).
Interestingly, Ostrovsky et al point to "new entrants such as Ask Jeeves and Microsoft Network [who] have a comparative advantage over the established players in implementing VCG" (page 7).
If MSN indeed goes with true VCG, it could have an edge over Google. But that still leaves Google's high click-through rates to be beaten.