We had this issue, and have managed to fix it like this:
1 - Add the user who previously had permissions to the mailbox to the msExchDelegateListLink attribute on the on-premises shared mailbox manually using Set-ADUser (based on this support article, Scenario 2)
Set-ADUser -Identity "distinguishedName of on-premises shared mailbox" -Add @{msExchDelegateListLink="<distinguishedName of user where mailbox is still appearing"}
2 - Perform an Azure AD Connect sync
3 - Wait 15-20 minutes for the change to replicate from Azure AD to Exchange Online
4 - Remove the user from msExchDelegateListLink once more
Set-ADUser -Identity "distinguishedName of on-premises shared mailbox" -Remove @{msExchDelegateListLink="<distinguishedName of user where mailbox is still appearing"}
5 - Perform an Azure AD Connect Sync
It seems that according to the support article above, on-premises Exchange does not set or remove msExchDelegateListLink when adding/removing permissions for in-cloud mailboxes, so you have to do it manually, instead of the usual fix of adding & removing the permissions. I found that after an third Azure AD Connect sync beyond those above, the user's entry in the cloudMSExchDelegateListLink attribute was cleared as required, the user's AutoDiscover XML no longer returned the mailbox, and the extra mailbox disappeared from the user's Outlook.