I discovered today that Outlook does not, by default, search the phone number fields in a contact.

I don’t understand why this would not be enabled by default, however here’s how to search for a phone number in Outlook:

• To search for a phone number, go to Advanced Search (Ctrl-Shift-F)
• On the Messages Tab, enter the phone number and change the “In” field dropdown to “Phone number fields only”

It took me a long time to find this, hopefully it will be easier for you.