Hints on running a well-configured outgoing mail server

If you do not have a static IP address, use your ISP's mail relay (smarthost).

Make sure that there is a reverse DNS (PTR) record for your IP address. Make sure that it is not generic (e.g. wylie.me.uk, rather than client-12-34-56-78.adsl.example.org). You will need to contact your ISP to do this. (See RFC1912 section 2.1)

Make sure that doing a PTR lookup, then doing an A lookup on that domain name gives the original IP address, e.g. $ host 82.68.155.89 89.155.68.82.in-addr.arpa domain name pointer wylie.me.uk. $ host wylie.me.uk wylie.me.uk has address 82.68.155.89

Get your ISP to SWIP your IP allocation, so that a whois lookup shows that it is allocated to you.

Make sure that your ISP has not listed your IP address as dynamic with any DNSBL, e.g. dul.dnsbl.sorbs.net. If necessary, get your ISP to contact the DNSBL maintainers and ask for your IP address to be delisted.

Make sure that your HELO/EHLO string is a FQDN (Fully Qualified Domain Name), e.g. "wylie.me.uk", rather than "NTSERVER", as required by RFC 2821 section 4.1.1.1

Further reading (This was originally written in 2006, some of these links may be out of date, I'm afraid):
SORBS
Spamhaus reverse DNS
Spamhaus Dynamic IP lists
Yahoo mail help
AOL Technical Standards for E-mail Delivery
AOL Reverse DNS
Messaging Anti-Abuse Working Group Sender Best Communications Practices