How can I search the Exchange Global Address Book by phone number?

It would be possible to use a Search in the Active Directory, itself.

Can you open "Active Directory Users and Computers" in your Domain? There you can choose at 'Advanced' the Field "Phone" and search there.