I'm going to take one for the team on this...
So you have hybrid Exchange and Office 365 and for some reason you wind up with an account with a local Exchange Mailbox and an Office 365 mailbox. After years of just delete the whole Office 365 account to fix the issue Microsoft finally gave us this:
Permanently Clear Previous Mailbox Info: https://blogs.technet.microsoft.com/exchange/2018/01/17/permanently-clear-previous-mailbox-info/
Great! That's awesome! I have a user right now that I need to fix. Wonderful. Glad I remember seeing that somewhere along the way.
{The actual command most people would use would be Set-User, but I use
the O365 prefix to my Office 365 powershell commands so as to not
clobber my local AD and Exchange powershell commands. -ED}
PS C:\Scripts\Exchange 2013> Set-O365User user@contoso.com -PermanentlyClearPreviousMailboxInfo
WARNING: The command completed successfully but no settings of 'user' have been modified.
What? Why not?
Why is Google only telling me of other people who are seeing this same error but now resolution?
Open support ticket. DELAY DELAY DELAY
Oh wait that user has an Exchange online license. Let's unselect that.
PS C:\Scripts\Exchange 2013> Set-O365User user@contoso.com -PermanentlyClearPreviousMailboxInfo
PS C:\Scripts\Exchange 2013>
Uhhhhhhhhhh... Genius! Well DUH! So there you are. I'm admitting that I made a pretty stupid mistake so you can read this and then not have to admit to anyone else that you did.