Outlook Search Bar

Hello,

At the top of Microsoft Outlook 2003 just under the menus, on the right of
the menu bar, there is a "Type Here to Find Contacts" prompt.

I have a client who has recently migrated to an Exchange Server, and none of
her contacts that she is adding since joining the server are showing up in
that search. All of her old ones still do.

How can I change the scope of that search?

Thank you,
Ian