Outlook 2003 on an Exchange Server (Rented space from 1and1.com).  

I use the "Find a Contact" in the Type a contact to find box on the standard
toolbar.  (The little white box where you can type a name to open the contact
without going to the contact).

All of the sudden it will not find contacts, specifically contacts without
an e-mail address (I have contacts for things like my 18 month old son, my
pizza place, travel rewards numbers etc...)  

I have used this feature for years and all of the sudden it seems to not be
working!

Thanks!