Email Router Fails to Send E-mail from Dynamics due to Permissions

When using the Dynamics 365 Email Router to send email from a Dynamics 365 instance, the email may go into a "Pending Send" state and never actually send:

The Dynamics Email Router exception logs may show the following error:

An error occurred while checking for outgoing email messages to process: https://disco.crm.dynamics.com/<OrgName>. System.ServiceModel.FaultException`1[Microsoft.Xrm.Sdk.OrganizationServiceFault]: User does not have send-as privilege. (Fault Detail is equal to Exception details:

ErrorCode: 0x8004480D
Message: User does not have send-as privilege.

This behavior may have worked without needing these permissions on earlier versions of the Dynamics 365 application. Due to changes introduced to the security model in certain iterations of versions 8.2.2 and 9.x, these permissions must be explicitly granted in order for the E-mail Router to send e-mails on behalf of another user.

The user sending this email must allow emails to be sent from other Dynamics users in their personal options:

The account being used by the Email Router must also have the "Send Email as Another User" permission within Dynamics:

Dynamics 365, version 9.0 Email Router

Microsoft Dynamics Email Router is deprecated

How to migrate from Email Router to Server Side Synchronization