It looks like Microsoft is trying to cut a deal with Verizon to put search service and related advertising on Verizon phones.
Full story here