Reuters is reporting that Microsoft, through proposed guaranteed payments, is nearing a deal with Verizon to become the carrier's default search provider:

Under the terms being considered, Microsoft would share with Verizon revenue from ads shown in response to cell phone Web searches, with guaranteed payments to the carrier of about $550 million to $650 million over five years, roughly twice what Google Inc offered, the people told the paper.

If Microsoft succeeds, it would replace a tentative deal with Google. I've written a bit more in my post on Search Engine Land.