This issue happens when Email Relay is set up in your Salesforce org and the IPs are not whitelisted properly in the email Server.

Go to https://help.salesforce.com/articleView?id=000003652&type=1 to find the IP ranges.

If you have enabled email relaying you will need to allow mail from the IP address which we use to send system email, Chatter and Communities mail, and those Salesforce uses for email relaying.

Sample IPs in the article: