Microsoft provides a free Global Address List (GAL) and Schedule+Free/Busy lookup utility for Windows Mobile 2003 based Pocket PC and Smartphone devices called Microsoft Global Contact Access.

With Microsoft Global Contact Access, you can:
-Search Exchange Server 2003 Global Address Lists (GAL).
-Schedule meetings with multiple recipients and include resources such as conference rooms.
-View the Free/Busy schedules of meeting attendees.

When installed, you will get a Find Contact Online option which will display the following fields from the GAL and is restricted to 100 entries per search result:

Title
Company
Work Telephone
Mobile Telephone
E-mail address
Office Location

Download Pocket PC version here and Smartphone version here