This will not happen if we create a shared mailbox on the cloud.
After some research and it was happen when the local domain @mydomain.local in the Office 365 User Email Address. you could try to search the email address.
1. Office 365 Admin Portal > Group > Shared Mailbox > Search and click on the User Name > Email aliases.
2. Office 365 Admin Portal > Admin Centers > Exchange > recipients > shared > Double click on the shared mailbox > Email Address.
In my Scenario I have an Active Directory, Azure AD connect and a demoted Exchange Server 2007. Since my Exchange 2007 server not working but i will show you the location in the Exchange server 2007 console.
Delete User Email address using ADDS.
1. Go to your AD Server > Active Directory Users and Computers > View > Select Advanced Features > Navigate to the User Account > Right click and select Properties > Attribute Editor.
2. Search for proxyAddressess > Double Click and remove
3. Go to Azure AD Server > Open Powershell > Perform a Delta sync from Azure AD Connect.
4. Go to Office 365 Admin Portal > Admin Centers > Exchange > recipients > shared > Double click on the shared mailbox > Email Address.
The Email Address should be remove and you can try to proceed to assign "Send As" user rights.
Delete User Email address using Exchange Management Console (2007)
1. Open Exchange Management console > Recipient Configuration
Before migration = Mailbox > Right click user's mailbox > Properties
After migration & Mail Enabled User = Mail Contact > Right click User's name > Properties
2. Go to E-mail Addresses > Remove address with @mydomail.local
3. Go to Azure AD Server > Open Powershell > Perform a Delta sync from Azure AD Connect.
4. Go to Office 365 Admin Portal > Admin Centers > Exchange > recipients > shared > Double click on the shared mailbox > Email Address.
The Email Address should be remove and you can try to proceed to assign "Send As" user rights.
Delete User Email address using ADSI Edit
* If you run MMC on client PC. You need to install RSAT to connect into the domain contoller
1. Open Run and type mmc
2. Go to File > Add / Remove Snap-in
3. Select ADSI Edit > Add > OK
4. Right Click ADSI > Connect to
5. Connect to Domain Controller by using Computer name or IP address
6. Navigate to the User Account > Right click and select Properties
7. Search for proxyAddressess > Double Click
8. Select the object @mydomain.local > Remove > OK
9. Go to Azure AD Server > Open Powershell > Perform a Delta sync from Azure AD Connect.
10. Go to Office 365 Admin Portal > Admin Centers > Exchange > recipients > shared > Double click on the shared mailbox > Email Address.
The Email Address should be remove and you can try to proceed to assign "Send As" user rights.
The Email Address should be remove and you can try to proceed to assign "Send As" user rights.