We migrated a number of shared and user mailboxes recently and found that after the migration users were getting the dreaded undeliverable message – upon checking EAC all looked fine in terms of permissions but as a troubleshooting step we added them again through powershell using the new O365 command for send as permission:
Add-RecipientPermission <Identity> -AccessRights SendAs -Trustee <Identity>
After this the function worked as expected!
Hope it helps.