All my emails to Yahoo!, Hotmail and AOL are going to Spam, though I've implemented every validation method (works for Gmail though)

In looking at your failures, I have noticed several problems.

The first is that the originating ip for your emails (208.115.108.162) is listed on Five Ten's blacklist (http://www.five-ten-sg.com). Yahoo, Hotmail, and AOL all use their own internal blacklists, and to my knowledge don't rely on third party blacklists (such as Five Ten). That being said, it's a good indicator that something is afoot. You can delist yourself at five ten here: http://www.five-ten-sg.com/blackhole.php?ip=208.115.108.162&Search=Search. Delistings usually take around 12 to 24 hours. While this won't necessarily FIX your Yahoo, Hotmail, AOL problem... you should delist pronto.

The biggest problem is the lack of MX record for gemini.shiftapp.com. The emails are "FROM" [email protected]. It is a very common anti-spam tactic to lookup the MX record of the sending domain on incoming email. When AOL etc lookup the MX record for gemini.shiftapp.com, and they see none... they will likely classify as spam on the spot. At the very least, an MX will allow the recipients of these emails to reply.

Reverse DNS: You have a valid PTR record for that IP. AOL etc just simply look to see that PTR records exist... they don't really care what the PTR record returns so you are "good to go" as they say.

I didn't find any SPF records for gemini.shiftapp.com or shiftapp.com. That's ok because SPF never really caught on. Kinda like 8 track or Laser Discs... they look good on paper, but never gained critical mass.

My bet is the lack of MX records. One other thing to consider: make sure your email server is not an open relay (allowing unauthenticated users to send mail to other users not hosted on your server). Also, might be wise to do an audit of all email going through your system... if one of your users is (knowningly or UNknowingly) sending spam through your server, you'll be skating uphill!

Hope this helps, and best of luck! -Chris

Have you checked with Yahoo/Hotmail/AOL and the various anti-spam blacklisting services? It's possible that a previous user of your IP was committing nefarious deeds with those digits.

According to this tool, your IP (208.115.108.162) is on the FIVETEN blacklist. According to their site, your IP is listed for the following reason: "IP address 208.115.108.162 is listed here as creditoffersite.com. Category: misc".

According to FIVETEN, the description of the misc category is:

misc - Miscellaneous includes (but is NOT limited to) the following groups. Note that this does NOT include misc.spam which is listed under spam above. 1) /24 blocks of addresses containing systems that are apparently sending bulk email (in volumes apparently comparable with the volume from AOL, Earthlink, Google), with any of the following attributes: missing or bogus reverse dns, reverse dns names in domains with no web server, or domains with boilerplate web content. 2) Systems that are strongly suspected of being multistage open relays (where I have not been able to identify the input stage) or open proxies.

According to Google's DNS servers, creditoffersite.com is now hosted at 72.20.40.25, but may at one point have been hosted at your IP, and committed some not-so-nice bulk emailing, or had issues with their mail relay.

Now, this isn't necessarily the reason AOL/Yahoo/Hotmail are blocking you, as this is only one blackhole list, and not a major one at all, but it's a possible clue to the ultimate issue. Another clue is things like this line from the Yahoo headers:

X-YahooFilteredBulk: 208.115.108.162

Contact AOL/Hotmail/Yahoo teams to get things resolved for sure.

Try this Email Server Test. If it checks out, contact the Individual service providers and join their Feedback loop program. That will give you some idea of why your emails are classified as SPAM.

I'll copy some of the content from my post over here.

Your email server may be on a blacklist or if you're on DSL it could look bad if it's too close to dynamic ranges (even if you have a static IP on "business class DSL"). Check the free tools on MXToolbox.com to see if any of those apply to you. Run the blacklist test at DNSBL.info as well.

Furthermore, are there any links that you have within the emails you're sending out? That can count against you as well. Ultimately, you'll have to take it up with the abuse team at each of the problem domains (as phoebus pointed out, whom I seem to be parroting today =) ).

First, as already stated - you should work towards getting yourself removed from any black lists (such as Five Ten's blacklist). You should also have an MX record for your domain in your "From Address" (it looks like you've already fixed this).

One thing I noticed in your Yahoo headers was an apparent invalid DKIM signature:

"dkim=permerror (bad sig)"

You may have something not quite right DKIM wise, which should be corrected.

port25.com provides a very useful tool for checking all your authentication methods. You can send a test email to "[email protected]" and you'll get a response back showing the results of each authentication check (SPF, DomainKeys, DKIM, Sender-ID, and Spamassassin). It took about 12 hours for me to get a report, so be patient.

Each of the providers you mentioned handles things differently. My understanding is that they often rely on internal blacklists as opposed to public lists. I've recently been through this with Yahoo and MSN (Hotmail) and the process was different for each. In my case I was literally 100% clean on all blacklists and have functioning and matching forward and reverse DNS, DomainKeys, DKIM, and SPF records. In addition to this, I only send a handful of personal emails a month (no mailing lists, subscriptions, or bulk emails of any kind). **None the less, email from me was still getting tossed into Yahoo's "Spam" folder and Hotmail's "Junk" folder. Point being - even if you're doing everything "right" you may still need to take proactive steps with these providers to get your email through.

Yahoo: When I'd email a Yahoo user their SpamGuard filter would add a "X-YahooFilteredBulk:" header to the email, which put it by default into the spam folder. For me, the key turned out to be filling out their Mail Bulk Sender Form. The process was a little peculiar because it's a form for describing what type of bulk email you send and it's really intended for legitimate bulk email senders (whereas I don't send any bulk email at all) - but this seems to be the way to reach the right folks. I just explained in the comments field that I don't send any bulk email and enumerated the steps I'd taken to comply with Yahoo's policies (DomainKeys, DKIM, SPF, ...etc). The form submission acted a little strange, so be sure you get a return page confirming your submission. I actually had to go back and fill in the "Other" fields in order to get the form to submit for some reason (it wouldn't let me leave any fields blank).

Hotmail: When I'd email MSN (Hotmail) users, their wasn't anything quite so clear in the headers (other than a "X-AUTH-Result: NONE" header). MSN keys in on the Sender ID protocol (uses SPF records). You can read about how to set it up here and fill out a form to be included in the program.

AOL: I didn't have any issues emailing AOL users, but I believe this is because they also make use of SPF records which I already had.