In case of email providers blocking emails: check blacklists (spamhaus.org etc.) if your server IP might be blacklisted (on a new site this could be due to the site that used this IP before). Use mechanisms like SPF, DomainKeys to allow email providers to validate your server. Ask your provider to enter the correct (non-default) parameters in the PTR record for reverse DNS lookup.

excerpt from "iionly"