Just a quick post in the hope this saves someone the time I spent today trying to resolve this issue.
I came across a problem today with a user support request where they had Full Access permission to another users mailbox and trying to remove that mailbox after the Full Access was revoked. The other mailbox would show up in the primary users Outlook folder pane, even though the permissions had been revoked in the Exchange Management Console.
There were a lot of articles talking about using ADSIEdit to drill down and remove the offending entry, but I thought there must be a better way and sure enough there is. By using the Exchange Management Shell you can do the following to rectify your issue:
Open an administrator instance of the Exchange Management Shell. Then type in the following command (Change the bolded entries below to suit your environment):
Add-MailboxPermission -Identity UserWhoseMailboxWasShared -User UserWithSharedMailboxInTheirOutlookProfile -AccessRights FullAccess -InheritanceType All -Automapping $false
Hope you found this helpful...