Outlook – How to search the Exchange Global Address Book by phone number

I think you'll find the auto-completion that pops up when typing names in to the To field is not doing an address book lookup - it's scanning a local cache that lists frequently/previously used contacts (from both global and local lists).

Here's a MS support article that explains how to reset the cache (in case of corruption, etc).
I don't know if it will help in your case, so obviously take backups.

You might also me interested in trying Ctrl + K after typing the first part of a name in - it's the shortcut key for Check Names and will either replace the partially-typed name with a full match, if there's only one, or pop-up a box suggesting the various matches in the case where it finds several. However, I've got a feeling (not confirmed) that this only works with the global list, not local.

If you are doing a search using Active Directory tools, then the * character is the one you would use for a wildcard, not %. This comes from the LDAP directory search syntax.

But it looks to me like the search box available from dsquery.dll only works correctly with a wildcard placed at the end of the string. So if you wanted to find groups with names beginning with "ABC" then you could search for them using:

ABC*

But searching using the following does not return any results:

*ABC*

This is a limitation of the dsquery.dll user interface (the same as what you get to by using "Active Directory Users and Computers"). The underlying LDAP directory search API allows for a wildcard to be placed on either the beginning or the end.

If you really need this functionality, then you might want to try using PowerShell. It's a full-featured scripting language from Microsoft and can be hard to learn if you've never done any scripting before. But it will give you all the flexibility you need. It is also fairly easy to get started with if you install the PowerGUI tool from Quest.

For any questions on writing and using PowerShell cmdlets or scripts, you would probably want to post a follow-up question on Stack Overflow.