Now available... new browser- and client-based versions of Live Search for Mobile.

Live Search for Mobile 

Visit http://mobile.search.live.com/about/ for more details on installing the application on your Windows Mobile devices (you'll also find a list of compatible devices listed for J2ME phones). You can install on Windows Mobile 2003 and later (WM5) fo raccess to Local Search, movie listings, maps and directions, and (for me, quite helpful) traffic updates.

And visit http://m.live.com via your mobile browser to use Live Search.