I'm getting very weird results here. When my server sends an email to my @hotmail or @gmail account, it's marked as spam. When I send email through my server from Outlook to @hotmail, it doesn't get marked as spam, but it still gets marked as spam in gmail. They seem to get through fine on Yahoo though.

My servers hostname A record points to an IP address whose PTR record points back to the same domain name. The TXT record has a SPF record in it to allow email to be sent from that servers IP.

I moved from a VPS to a Dedicated server when this started to happen. From what I can see, the email headers are identical. Here's one of my email headers that gmail marks as spam. Some fields were repalced.

MYGMAILACCOUNT is the email address of the account the email was addressed to.
USER is the name of the account on the system it was sent from
HOSTNAME is the servers FQDN
IPADDR is the IP Address of the Hostname
MYDOMAIN is my domain name

Delivered-To: MYGMAILACCOUNT
Received: by 10.220.77.82 with SMTP id f18cs263483vck;
        Sat, 27 Feb 2010 23:58:02 -0800 (PST)
Received: by 10.150.16.4 with SMTP id 4mr3886702ybp.110.1267343881628;
        Sat, 27 Feb 2010 23:58:01 -0800 (PST)
Return-Path: <USER@HOSTNAME>
Received: from HOSTNAME (HOSTNAME [IPADDR])
        by mx.google.com with ESMTP id 17si4604419yxe.134.2010.02.27.23.58.01;
        Sat, 27 Feb 2010 23:58:01 -0800 (PST)
Received-SPF: pass (google.com: best guess record for domain of USER@HOSTNAME designates IPADDR as permitted sender) client-ip=IPADDR;
Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of USER@HOSTNAME designates IPADDR as permitted sender) smtp.mail=USER@HOSTNAME
Received: from USER by HOSTNAME with local (Exim 4.69)
    (envelope-from <USER@HOSTNAME>)
    id 1Nle2K-0000t8-Bd
    for MYGMAILACCOUNT; Sun, 28 Feb 2010 02:57:36 -0500
To: Ryan Kearney <MYGMAILACCOUNT>
Subject: [Email Subject]
MIME-Version: 1.0
Content-type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
From: webmaster@MYDOMAIN
Message-Id: <E1Nle2K-0000t8-Bd@HOSTNAME>
Sender:  <USER@HOSTNAME>
Date: Sun, 28 Feb 2010 02:57:36 -0500
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname - HOSTNAME
X-AntiAbuse: Original Domain - gmail.com
X-AntiAbuse: Originator/Caller UID/GID - [503 500] / [47 12]
X-AntiAbuse: Sender Address Domain - HOSTNAME

Anyone have any ideas as to why all mail leaving my server gets marked as spam?

EDIT: I already used http://www.mxtoolbox.com/SuperTool.aspx to check if my servers IP's are blacklisted and they are in fact not. That's what I thought at first, but it isn't the case.

Update Mar 1, 2010 I received the following email from Microsoft

Thank you for writing to Windows Live Hotmail Domain Support. My name is * and I will be assisting you today.

We have identified that messages from your IP are being filtered based on the recommendations of the SmartScreen filter. This is the spam filtering technology developed and operated by Microsoft and is built around the technology of machine learning. It learns to recognize what is and isn't spam. In short, we filter incoming emails that look like spam. I am not able to go into any specific details about what these filters specifically entail, as this would render them useless.

E-mails from IPs are filtered based upon a combination of IP reputation and the content of individual emails. The reputation of an IP is influenced by a number of factors. Among these factors, which you as a sender can control, are:

• The IP's Junk Mail Reporting complaint rate
• The frequency and volume in which email is sent
• The number of spam trap account hits
• The RCPT success rate

So I'm guessing it has to do with the fact that I got an IP address with little or no history in sending email. I've confirmed that I'm not on any blacklists. I'm guessing it's one of those things that will work itself out in a month or so. I'll post when I hear more.