(1) Do you have an OAB configured on your Exchange Server?
(2) If you already have one configured, does rebuilding the OAB from within Exchange System Manager (Recipients | Offline Address Books | Right-click | Rebuild) followed by an Information Store Service restart (during a maintenance window of course!) correct the problem?
(3) If the first two suggestions don't resolve the problem, have a good read through the following Microsoft Knowledge Base Articles -- 273364 and Q275171 to see if rebuilding the OAB System Folder corrects the situation.
This was first published in June 2004