Mail from Plesk server is rejected with error: 550-5.7.1 is likely unsolicited mail

Symptoms

Mail forwarded to Gmail is rejected:

CONFIG_TEXT: Our system has detected that this message
550-5.7.1 is likely unsolicited mail. To reduce the amount of spam sent to
550-5.7.1 Gmail, this message has been blocked. Please visit 550-5.7.1
http://support.google.com/mail/bin/answer.py?hl=en&answer=188131 for 550
5.7.1 more information. ho13si622251wib.49 - gsmtp (in reply to end of DATA
command)

OR

CONFIG_TEXT: MailEnable: Message could not be delivered to some recipients.
The following recipient(s) could not be reached:
Recipient: [SMTP:john.doe@example.com]
Reason: Remote SMTP Server Returned: 550 See http://spf.pobox.com/why.html?sender=***(#5.7.1) 

The following error log can be found in /var/log/maillog :

CONFIG_TEXT: postfix/smtp[4907]: 02A25158106B: to=<john.doe@example.com>, relay=mx1.example.com[193.105.38.150]:25, delay=22, delays=0.45/0.04/10/12, dsn=5.7.1, status=bounced (host mx1.example.com[203.0.113.2] said: 550 5.7.1 <john.doe@example.com>: Recipient address rejected: Please see http://www.openspf.net/Why?s=helo;id=example1.com;ip=203.0.113.3;r=mx1 (in reply to RCPT TO command))

Similar issue may occur with other public mail services, like Hotmail etc.

Cause

SPF record is not set properly.

Resolution

Log into Plesk and recheck syntax of SPF record in Domains > example.com > DNS Settings.
SPF record can be verified according to the article How to check whether a domain has a correctly set SPF record? or using 3rd-party services like mxtoolbox.com

If a domain doesn't have SPF record, add it at Domains > example.com > DNS Settings > Add Record - Record Type TXT "v=spf1 +a +mx -all" or via SSH/RDP connection: 

on Windows :

C:\> plesk bin dns --add example.com -txt "v=spf1 +a +mx -all"


on Linux :

# plesk bin dns --add example.com -txt "v=spf1 +a +mx -all"

Note: if SPF record was updated recently wait till proper SPF record will be propagated