Yahoo flagging mail as spam when using relay server

I'm using Postfix to relay mail from my site to my mail server. Mail is received properly at my Gmail and Hotmail accounts - only Yahoo is the problem. The Yahoo mail headers state:

Received-SPF: none (mta1133.mail.mud.yahoo.com: domain of [email protected] does not designate permitted sender hosts)

In contrast, the Gmail headers state:

Received-SPF: pass (google.com: domain of [email protected] designates 74.50.xxx.xxx as permitted sender) client-ip=74.50.xxx.xxx;

Reverse DNS is set up correctly, as is my SPF record and domainkeys/dkim (both domainkeys and dkim show pass(ok) in the Yahoo mail headers).

Does anyone have any suggestions as to what I can do to solve the Yahoo problem (short of contacting Yahoo, as this is a brand new mail server)?

Thanks

Solution 1:

In MX Toolbox I get (for domain: vitalmtb.com): Warning - Reverse DNS does not match SMTP Banner (this could mean that PTR record for your domain is not correct or your HELO banner doesn't match your PTR record. Perhaps Yahoo doesn't like that? Good luck!