Unable to send an email from a Plesk server to Gmail: 421-4.7.0 This message does not have authentication information or fails to pass 421-4.7.0 authentication checks

Symptoms

Emails sent to Gmail are stuck in the mail queue and the following error message appears in /var/log/maillog:

421-4.7.0 This message does not have authentication information or fails to pass 421-4.7.0 authentication checks

550-5.7.26 This message does not have authentication information or fails to.

Cause

DKIM/SPF support is disabled for the domain.

Resolution

Enable DKIM and SPF support for the domain.