I have a single contacts folder, and address are properly located when
sending e-mails and viewing the address book with one exception.

I have historically used the 'Contact Search' toolbar to find any contact.  
In Outlook 2003, it seems that it only finds contacts which have an e-mail
address or FAX number.  I have a large number of contacts with only phone
numbers, and these addresses are not found when I search for a name in the
contact toolbar, but are clearly there when I use the 'Find' command on the
contacts folder, or type the first few letters of the 'file as' name when
viewing the contacts folder.  Bug?