Unable to set up a "Send mail as" address

Problem

While trying to set up a Send mail as address you get the error:

Functionality not enabled. 
You must send through gmail.com SMTP servers when you send as YourEMAIL@google.com. However, this functionality is not available for your account. Please contact your domain administrator for more information.

Environment

Gmail
Send mail as

Solution

By default, outbound gateway use is disabled. The Google Workspace mail servers deliver all outgoing mail, including mail that uses alternate From addresses.

Log in to the Admin console.
Navigate to Menu > Apps > Google Workspace > Gmail > End User Access.
In the Allow per-user outbound gateways section, select Allow users to send mail through an external SMTP server when configuring a From address hosted outside your email domains.
- When this check box is selected, users who associate additional email addresses with their accounts can enter connection information for an alternate SMTP server. Learn more about the required steps for the user.
- When the check box is not selected, users cannot specify an SMTP server for the additional address.
At the bottom, click Save.

Notes

Requires having the Gmail Settings administrator privilege or a super admin role.
Changes can take up to 24 hours but typically happen more quickly.

Cause

Users were not allowed to use their individual outbound gateways.