Problem
Typically you will get a "Undeliverable" with the error: "0x80070005-0x000004dc-0x00000524". This means that this is an Outlook client problem. The user would be able to send from Office online (OWA) but cannot send from Outlook.
Fix
Remove Cache mode from Outlook 2016.
Step One: Open Outlooks' Account Settings
1. File -> Info -> Account Settings
2. Press Change on the user's mailbox.
Step Two: Turn off Cached Exchange Mode
1. Uncheck the checkbox Use Cached Exchange Mode to download email to an Outlook data file.
2. Press Next.
Step Three: Restart Outlook
After restarting Outlook the user should be able to use their "Send As" permissions.