This will be the goto to help solve e-mail delivery issues and talk about many practical issues that happen between developers, admins and scripts that send e-mail and do things that may not be acceptable or cause deliverability problems.
Sendmail Stuff
Edit /etc/mail/sendmail.mc
The problem is that if you send directly out from the server using the mail function, the Return-path of the e-mails will be username@thehostnameoftheserver.com. Let........
Jul 11 15:20:58 tor sendmail[9617]: r6AKjOD07: to=
mailserver.com was the hostname of the server, sendmail sends this by default and many mailservers will reject mail to a hostname that does not resolve or exist.
The easiest way is just to change the hostname and make sure it does resolve to something.
I read there is a way in sendmail.mc to manually set a hostname but I never got it working:
vi /etc/mail/sendmail.mc
define(`confDOMAIN........