Work recently purchased me a Verizon XV6700 Pocket PC (running Windows Mobile 5) so that I could better keep in touch w/our server farms. It's been an interesting 2 weeks playing w/the phone. I'm still learning the ins and outs of it using a PDA phone. It's definitely powerful, but it lacks a lot of "normal" cell phone functionality out-of-the-box. I'm planning on writing a full review later.
Anyway, Microsoft has released a version of Windows Live Search for the PPC. It's pretty darn slick. It's a shame you can't use aGPS with the mapping functionality, but this program runs very well on WM5. I'd definitely recommend checking it out.
I've heard the J2ME version doesn't work as well as Goolge Maps for J2ME, but the version designed especially for Windows Mobile runs exceptionally well (at least so far, I can't say there aren't any slow memory leaks w/my limit usage.)
Jenn & I are headed to Pittsburgh this weekend, so I think Windows Live Search will come in very handy this weekend. They even have live traffic reports for Pittsburgh. It's a shame they don't do them for Columbus, OH yet.