From the press release Microsoft Announces Three New Windows Live Products for Mobile Devices we learn

Today at 3GSM World Congress 2007, Microsoft Corp. announced three new Windows Live™ for mobile services that provide search and communications capabilities to help people access their world of relationships, information and interests from their mobile device. Now available in the United States and the United Kingdom, Live Search for Windows Mobile^® and Live Search for Java provide customers with advanced local search and mapping capabilities on their mobile device. In conjunction with the availability of Windows Mobile 6, Microsoft also introduced Windows Live for Windows Mobile — a rich set of Windows Live services including e-mail, instant messaging and search — uniquely designed to work with Windows Mobile powered devices.

You can download the search clients for Java or Windows Mobile phones by going to http://mobile.search.live.com/ from your desktop or http://wls.live.com/ from your phone. I downloaded the client app onto my Cingular 3125 and it is quite snazzy. Traffic and local business search in my phone, all for free. My only gripe is that there doesn't seem to be GPS integration in the local results presented which may be a limitation of my phone as opposed to the software.

It looks like you can only get Windows Live for Mobile with integration with Windows Live Spaces, Windows Live Hotmail and Windows Live Messenger when you get a new Windows Mobile phone with Windows Mobile 6.0 or can figure out how to upgrade your phone's OS. In the meantime, you can drool over the features at official website for Windows Live™ for Windows Mobile®.