"Email can't be received because the license is invalid for the mailbox" error occurs in Dynamics 365

After clicking the Test & Enable Mailbox button in Dynamics 365, the Incoming Email Status shows as Failure and an alert is logged with the following details:

"Email can't be received because the license is invalid for the mailbox <Mailbox Name>.

Email Server Error Code: ErrorInvalidLicense"

This error can occur if you are attempting to connect to an Exchange Online user mailbox and that user/mailbox does not have an Exchange Online license assigned.

Assign an Exchange Online license to the user/mailbox. Click here for more information about how to assign licenses in Office 365.

NOTE: If the purpose of the mailbox is to function as a Queue and not a User, it is recommended to use a Shared mailbox in Exchange. Shared mailboxes do not require an Exchange Online license. If you open the Exchange admin center, click recipients, and then click shared, check to see if the mailbox appears in this list. If the mailbox is a regular mailbox and you select it, you will see an option to convert to shared mailbox.

If you click to view the Details within the Alert, you see details similar to the following:

ActivityId: <GUID>
>Error : <ResponseMessageType xmlns:q1="http://schemas.microsoft.com/exchange/services/2006/messages" p2:type="q1:FindItemResponseMessageType" ResponseClass="Error" xmlns:p2="http://www.w3.org/2001/XMLSchema-instance"><q1:MessageText>An internal server error occurred. The operation failed., Mailbox '<Mailbox ID>' doesn't have a valid license.</q1:MessageText><q1:ResponseCode>ErrorInternalServerError</q1:ResponseCode><q1:DescriptiveLinkKey>0</q1:DescriptiveLinkKey><q1:MessageXml><t:Value Name="InnerErrorMessageText" xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types">The license is invalid for this mailbox.</t:Value><t:Value Name="InnerErrorResponseCode" xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types">ErrorInvalidLicense</t:Value><t:Value Name="InnerErrorDescriptiveLinkKey" xmlns:t="http://schemas.microsoft.com/exchange/services/2006/types">0</t:Value></q1:MessageXml></ResponseMessageType>