Why does my mail server refuse to relay?

Modern (ie, not slackware) distributions including Redhat ship sendmail configurations that deny relaying by default. If you wish to use your linux box as an SMTP server, you will need to tell sendmail who may send mail through your server.

Do not open it up completely. Spammers regularly scan for such boxes and use them to hide their tracks while doing their evil deeds. Worse, the various blacklists around do scanning also, and if you get onto the blacklist you will be unable to send mail to any site that subscribes to the dynamic blacklist server concerned. Don't do it.

Edit /etc/mail/relay-domains and include the IP addresses, subnets and/or domains that may use your machine as a relay. Typically this would just be the subnet of the ethernet adapter on that machine.

Example: If you have the class C subnet 192.168.1.0 behind your server, put the line 192.168.1 in /etc/mail/relay-domains

Note: Older systems may use a different name for this file. A common such alternative is /etc/mail/relay_allow.

Don't forget to restart the sendmail! On redhat boxes, execute /etc/rc.d/init.d/sendmail restart. If sendmail is your MTA on your debian box, execute /etc/init.d/sendmail restart. killall -1 sendmail will probably not work.