In early 2008, new changes were added to these email providers in the strict rules used to accept email from these providers. Â The exact details are secret, but what we do know is that SPF records are now a more important factor in these rules.
You can use google to inquire about other people with these issues (you're not alone). Â A few more descriptive results:
http://owahab.com/content/delivering-emails-gmail-yahoo-and-hotmail
http://www.webhostingtalk.com/showthread.php?t=686676
Lets start off with a quick overview of what an SPF record is. Â An SPF record is simply a TXT type dns record which is used to store information about what IPs are allowed to send email for a specific domain. Â Â A receiving mailserver can do a lookup on this TXT record get get this data, and use the information to decide if an IP sending email from a specific domain really is allowed to be sending email for that domain.
There are a few options you can use with SPF records to govern the severity of encforcement on these rules.
Details on these rules can be found here:http://www.openspf.org/SPF_Record_Syntax
By default (as of May 12, 2008), DirectAdmin uses the ?all  value for it's SPF records.
This means that all receiving mailservers should be neutral about who is allowed to be sending mail for a domain.
For example, mail would be allowed to come from your DA box, and allowed to come from your clients ISP mailserver (since many ISPs block all smtp traffic out execpt from their own servers). Â This is why we use a default of ?all, so that it's more allowing of mail from different locations, since many users simply don't have the ability to send through their DA server. Â (Note: using port 587 instead of 25 to the DA box is the current workaround for that, which is recommended for this fix).
Now these big email providers don't like this email sending neutrality. Â They want to know for sure that a sender is correct, so they assume that any domain sending email with a neutral SPF record must be spam, thus your emails end up in their spam folders.
The solution is to setup your SPF record to use the -all option insetad of the ?all option so that email can *only* be sent from your server. Â This means that you *must* get all of your clients to send their smtp through your server, or they will be tagged as spam for spoofing. Â If they're blocked on port 25 to your server, tell them to send on port 587 to your server (same thing, just not block by the ISP)
To setup a value of -all, you can either change your DNS zone manually from:
Admin Level -> DNS Administration -> domain.com
or User Level -> DNS Management
change:
"v=spf1 a mx ip4:1.2.3.4 ?all"
to be"v=spf1 a mx ip4:1.2.3.4 -all"
of course, where 1.2.3.4 should be replaced by your server IP.If you'd rather do this to all of your domain, you can use perl
cd /var/named
perl -pi -e 's/\?all/\-all/' *.db
If you want this to be your default for new domains, type:
cd /usr/local/directadmin/data/templates/custom
cp ../dns_txt.conf .
perl -pi -e 's/\?all/\-all/' dns_txt.conf
Restart named after making the changes. Â Allow at least 4 hours for the new records to propogate (possibly more if they ignore the TTL values)
There are other basic things on top of the SPF records, like making sure your hostname resolves, and that your server IP has a reverse IP lookup (see How to setup the Mail System)
More information about this will be added as it becomes known.
Enabling DKIM in Exim is known to reduce the chance of your emails being flagged as spam, when sending to servers who check it (gmail, hotmail, etc..)