The somewhat popular Windows Live Mobile Search, specifically crafted for PDAs running Windows Mobile, has received good reviews in the past. Now, they are releasing a new version of the engine, making Live Mobile Search V2 available.
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.