Have you tried resetting the Outlook Address Book Service?
http://home.indy.rr.com/russval/addressbook.htm#Lose

--
Russ Valentine
[MVP-Outlook]
"Mike Smith" Mike wrote in message
...
Even though I have many contacts in the My Contacts part of Outlook 2003,
when I search for one of these contacts using the "Find a Contact" toolbar
search box in the "Mail" view, it fails with "Outlook could not find the
requested contact." If I go to My Contacts and use the Find button to
search
for the same text, it correctly displays the contact. It feels like the
"Find
a Contact" toolbar search box in the "Mail" view is wired to look in the
wrong place, but I don't know how to fix it.

Any help or hint would be greatly appreciated! Thanks in advance.