Every once in a while I see this issue when someone is using cached mode and for some reason the offline address book on their pc outlook client is not synching properly. Check their outlook for synch issues. You may also see offline address book errors on the exchange server where their mailbox is located. Take the outlook client off cached mode and have them try again to confirm issue. They can delete the OAB file and do a send/receive which will rebuild it. But if they are having synch issues you will need to help them resolve those.