Whether you are using a java-based phone or a Windows Mobile based phone, you can try the new engine out. As before there are is a web-based version and a client app, the latter of which is the most integrated.
For a mobile application, it is actually fairly impressive on the client end, especially with the mapping and directions. If you have a PDA, it's at least worth a look. You can read more about the engine at Microsoft's site.