Ran across this twice recently so I’m putting it here for possible future reference.
The last troubled mailbox had somehow gotten corrupt and when trying to recover/rebuild it somehow also Outlook Address Book had gotten corrupt. Following these instruction was a piece of cake to remove the old broken OAB and rebuild it fresh.
If you attempt to address a new message from your Contacts, you may receive the following error message:
The address list could not be displayed. The Contacts folder associated with this address list could not be opened; it may have been moved or deleted, or you do not have permissions. For information on how to remove this folder from the Outlook Address Book, see Microsoft Outlook Help.