Version? How did you write the advanced search criteria?

In advanced find, you need to choose one type of phone number (advanced tab)
and can only search that number type - you can't search all phone fields or
add two or more phone fields to the search to do an OR search (business
phone contains 23 or home phone contains 42). It works for partial numbers
and you can search for 'business phone contains 42 or 23' though.

Outlook 2007 can do it using instant search.