If you’re sending mail to a host that has strict HELO checking turned on (30-40% spam reduction currently) and your server is behind a firewall, and you’re using sendmail, odds are your sendmail is going to be sending an invalid (as far as the world is concerned) hostname and your mail will be rejected.
First, try the sendmail smarthost option. If it works for you, great, you’ll be relaying mail properly. Somehow I’ve never had it work for me, in myriad situations.
If you’ve moved beyond that, you probably have the sendmail.mc MASQUERADE macros setup already, and you might logically assume that would take care of HELO for you, but it doesn’t.
To solve this problem, you need to modify the Dj macro in sendmail. On my machine (trixbox, an asterisk distro, which is CentOS based, which is RedHat RHEL based, which is Fedora based) I found it in /etc/mail/sendmail.cf and /etc/mail/submit.cf. It’s my hope that submit.cf doesn’t get whacked when you make the sendmail.mc file, which can happen on boot or restart, so edit the submit.cf file.
Find the section with sample Dj macros and add one. Mine looks like:
Djlibrescu.bfccomputing.com
OK, so restart sendmail with /sbin/service sendmail restart and watch the mail flow in.
If you’re so blessed to be running postfix instead of sendmail, just add:
myhostname = librescu.bfccomputing.com
to the main.cf file and you’re done.