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

Using Plesk Interface

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?

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"

Using SSH/RDP connection

Connect to the server via SSH/RDP and execute the following command in Command Line or Linux Shell: 

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 12-24h