If this were happening to me, I'd remove the Outlook Address Book service
from the mail profile, stop and restart Outlook, and then add the service
back in.  We'll need to know your Outlook version to describe the exact
steps if you don't know how.