This could be an issue with the Offline Address Lists. Try rebuilding it:
- Open Exchange System Manager (ESM).
- Go to Recipients -> Offline Address Lists.
- Navigate to Default Offline Address Lists.
- Right click and select Rebuild.
MEMBER FEEDBACK TO THIS ASK THE EXPERT Q&A:
If Exchange cached mode is enabled in Microsoft Outlook 2003, try disabling it.
Exchange cached mode is supported on Exchange Server 5.5 and later, but the end user experience may vary unless Exchange Server 2003 or later is deployed.
As Exchange Server 5.5 is no longer under support, you should consider an upgrade to Exchange Server 2003 or Exchange Server 2007; Microsoft has many tools, processes and planning documentation to facilitate the move to Exchange 2003.
Do you have comments on this Ask the Expert Q&A? Let us know.
Related information from SearchExchange.com: