Verizon Wireless (NYSE: VZ) is in final stages of a deal with Google (NSDQ: GOOG), working on a comprehensive search deal, reports WSJ...Google will be the default search provider on Verizon devices and give it a share of ad revenue. The deal isn’t yet final yes, the story says, and the two sides are still negotiating on key issues such as Google’s desire to save information from user cellphone searches…that would be tricky, for sure. Interestingly, Medio, which is already working with VZW on, will be managing the all-in-one search, searching the phone’s content, the deck’s content and open-Web. That gives the Seattle based search company new relevance, and who knows, maybe even be bought by Google in the long term.

The Google search could be on the VZW homescreen. Later on, the deal could extend to Verizon’s Web portal and even its FiOS TV service, the story says. This would be a thawing of relationship between the two giants: Verizon is the only operator that has publicly dismissed Google-backed Android initiative. Also, during the spectrum auction earlier this year, Verizon was the biggest critic of the open-spectrum plan that Google heavily pushed for.

This a good deal overall in simplifying the mobile search market. But as phones open up, users will be able to use whichever search engine they desire, not the ones deemed official by the carriers. Witness this smart move by Yahoo (NSDQ: YHOO) for its OneSearch product and a shortcut on the homescreen of Nokia (NYSE: NOK) S60 devices. Where’s the carrier here? Sure, this is only for a minority of the users now, but surely it will become a lot more common and easier, as easy, hopefully, as choosing whichever search engine you want to go to on your PC.

For now, in this early days of mobile search, such exclusive deals abound: Sprint (NYSE: S) Nextel is working with Google and recently added it as the default search bar on browsers in over 40 of its phones. AT&T (NYSE: T) users Yahoo.

By the way, what happened to that supposed Google-VZW talks on using Android?