Try not to put your mail server in what people might consider a "dynamic IP" range.
Make sure that you are not using a CNAME? to deliver to. For example mail to foo@fishbowl.example.com will not work if fishbowl.example.com is a CNAME? to some other machine.
Don't set an MX? to point to an IP address! It won't work. MX?s must point to a record which contains an A? or an AAAA? RR. Not a CNAME?, not anything else.
Make sure that the reverse lookup of your outgoing mailserver exists, make sure has a matching forward record, and where possible, make sure that your HELO/EHLO name matches the reverse. Note, that this usually doesn't match the name of the domain you want to recieve mail for.
Don't use an underscore "_" in your domain name for mail, in your HELO/EHLO or 250 server greeting. Mail will get dropped.
Make sure you send mail from a domain that exists, and has at least an A?/AAAA? or MX? record. If you use an internal mail domain that doesn't actually exist, and mail from this internal domain somehow gets onto the Internet, you will lose mail.
Use 
http://dnsreport.com/ to verify that your DNS is in good healthy working order.
Attempt to publish a SPF record for your domain.
Secondary MX?s have fallen out of favour in recent years as the InterNet is more reliable and there are techniques for keeping your primary up (such as load balancing NATs). Having a secondary MX? is good if your connectivity is unreliable but a pain otherwise.
Be aware that spammers regularly send to secondary MX?s directly to avoid aggressive RBL checks on the primary MailServer. This can be exploited by having a secondary MX? that always returns a 400 series code (temporary failure), or is stricter with its RBL checks. Another trick is to list your primary MX? again as the highest number MX? so that spammers hit that one first.
Regularly check that your backup MX? still correctly relays. You won't notice a backup MX? rejecting mail until the first time your primary goes down and all your mail is immediately bounced rather than retried later.
Unless you can do challenge/response authentication, you should make sure your SMTP server supports SSL as outlined above. The easiest authentication to get working with SMTP is PLAIN or LOGIN authentication.
See EximSmtpAuth for information about configuring Exim for it.
Make sure that your smtp server supports SSL (even if you don't have a certificate), it should do STARTTLS to SMTP servers that support it.
If you use Exim with Debian stable, install the exim-tls package. For Debian testing/unstable (see FlavoursOfDebian), Exim already supports TLS by default.
If you have an SSL certificate, then make sure that Exim knows about it (and that your MX?s match the name on the certificate!) so that incoming connections can be SSL encrypted if necessary.
If you relay for other machines, you should set up SSMTP (SMTP over SSL) on Port 465/TCP. This is important in particular for laptops which may be used at a hotel, cybercafe or over wireless where port 25 outgoing may be blocked. MUAs should be configured to use SSMTP where possible.
Make sure you have a postmaster@ and abuse@ Email addresses that have the least number of filters (Spam, Virus, etc) on them. People may try to send you mail to notify you that your machine is broken and explain how you can fix it, but if you treat all mail from their machine as invalid, you'll never hear about the problem.
Make sure you've read http://kmself.home.netcom.com/Rants/avspam.html
Try to run an IDENT server on your mail server. Several mail servers still try to check IDENT by default. If you don't have IDENT enabled, then make sure you don't just drop packets to the IDENT port, or you will cause other MailServers to wait for a time out before they let you send any Email, slowing everything down.
One page links to SMTPBestPractices:
