Since aprox Sept 2004 there is a new headache for mail server administrators but it is not sure whatever it has the same effect on spammers , like it was intended to , and it’s name is SPF .
It is part of a set of rules that work for the purpose of stopping spam , and it is claimed that in the future all the mail your server send will be seen as spam if you do not implement SPF into your DNS records
There is a new SPF version out that makes use of microsoft’s proprietary Sender ID , which makes it unimplementable in any GNU software , but the classic SPF implamentation does not and is widely implemented in many opensource infrastructures.
You can use a SPF wizard on http://spf.pobox.com/ to generate your TXT record for spf , then add that record to your existing DNS records , that is if you have the ability to add TXT records to your DNS server .
Once you do that here is a tool to test your domain for SPF compliancehttp://www.dnsstuff.com/pages/spf.htm