The RedHat distribution of Linux often misconfigures the /etc/hosts file which can prevent Sendmail from working correctly. This may also affect other Linux distributions, but my main experience is with RedHat so I don’t know about the others.
Please note: this article is now several years old and relates to RedHat versions 8 and 9. The issues talked about here are unlikely to still be present in the more recent releases of RedHat Enterprise Linux and Fedora. (Fedora was the successor to the standard Redhat desktop distribution).
If you are getting lines like the following in your maillog file (at /var/log/maillog) mentioning that the connection is refused for mail processed by sendmail, then the solution may be to check this file. Obviously the dates and domains etc used in the lines will not necesarily be the same that you get, but it is an indication of the problem.
May 27 10:32:48 toolbox sendmail[30027]: h4QMWi7p030027: to=blackhole@electrictoolbox.com, ctladdr=chris (500/500), delay=00:00:04, xdelay=00:00:00, mailer=relay, pri=30031, relay=localhost.co.nz. [203.79.64.76], dsn=4.0.0, stat=Deferred: Connection refused by localhost.co.nz.
May 27 10:17:07 toolbox sm-msp-queue[29330]: h4QDLk2l023752: to=blackhole@electrictoolbox.com, ctladdr=nobody (99/99), delay=08:55:21, xdelay=00:00:00, mailer=relay, pri=930165, relay=www.somerealdomain.co.nz., dsn=4.0.0, stat=Deferred: Connection refused by www.somerealdomain.co.nz.
In this example, the Linux box is attempting to send mail to blackhole@electrictoolbox.com using the relay "localhost.co.nz" which does not exist. What happened was that the /etc/hosts file contained incorrect entries for the 127.0.0.1 entry and changing it so it only contains the following fixed the problem:
127.0.0.1 localhost localhost.localdomain
I have also noticed this problem when the actual domain name of the machine is in the /etc/hosts file as a 127.0.0.1 entry as in the example below. Removing these entries (so it’s like the above example) also solved this problem.
127.0.0.1 blackhole.electrictoolbox.com blackhole localhost localhost.localdomain