Slow searching on contacts

We have a couple of users that have local contacts as the first place to search and then the global address list. It takes upwards of 15 to 30 secounds for the seach to resolved the name put into the TO field. Sometimes it does not resolved a known name at all.

We are running Office 97 SP2 with Outlook 2000. Exchange is our e-mail server and were running on Windows 2000Pro.

Any suggestions?