While talking with Rob today, I was surprised to hear that he hadn't yet downloaded Window Live Search for Mobile Beta.  Usually he's the first person to try this stuff, so clearly the word hasn't spread as far as it should.

If you're using Google Mobile on your phone, you should switch right now (ask Gizmodo).

Yes, it works on J2ME phones as well as Windows Mobile.  I just used it on my Treo to find out the directions to Peet's Coffee.

I wish I had downloaded it yesterday when I got that flat tire.

p.s. don't forget to look at Windows Live Search blog.  One tip they mention: SMS a query like "Coffee 98040" to 95483 (WLIVE) and get back the results from any phone.