Originally Posted by till
1) Make sure that your server is run on a static IP address.
2) Check if your server is blacklisted: http://www.mxtoolbox.com/
3) Create SPF Records for your domains in DNS.
4) Make sure that the IP address of your server has a correct reverse dns record.
is an example for records to be created in ISPConfig