IP address is getting blacklisted constantly by spam filters on Plesk

Symptoms

1. IP address of a domain example.com is getting blacklisted constantly by spam filters.

2. Option Send from specified IP addresses is selected in Plesk > Tools & Settings > Mail Server Settings:

3. Domain example.com and hostname of the server hostname.example.com resolve to different IP addresses:

# dig +short example.com
203.0.113.2
# dig +short hostname.example.com
203.0.113.3

Cause

Expected behavior. According to official Plesk documentation:

“Send from domain IP addresses – Selecting this option may result in mail sent from some or all domains being marked as spam if the Plesk server host name fails to resolve properly, or if the domain’s IP is different from the one to which the Plesk server host name resolves.”

Resolution

Log in to Plesk and choose one of other options for Outgoing mail mode at Tools & Settings > Mail Server Settings: