Craig's really hit the nail on the head here. Buts its even worse than what Craig says. Just because we host say 1000 domains for incoming mail doesn't mean that only 1000 domains outbound through us. A customer with a domain name that is with another company for MX may still want to outbound mails from that domain through our SMTP server. SPF records and DKIM records would be needed for many thousands of domain names.

In saying that, for the past 12 hours we've had no issues with having emails accepted by Yahoo/Xtra. mx1 and mx2 are both accepting emails. In case this is handy to anyone else here is what we have done to remedy this issue (I'll list in order of likelihood in my opinion):

-We did nothing but wait another day - during this time mx2 started to trust us.

-I filled out this form -�http://help.yahoo.com/l/us/yahoo/mail/postmaster/bulkv2.html�- this is designed for "bulk mail-out senders" (spammers) to use, but it may have helped. We've received no acknowledgement from filling out this form other than the initial automated one.

-As mentioned we emailed postmaster@xtra a few days ago. I've received no response to this email but maybe its been silently dealt with.

-Potentially someone lurking on NZNOG got this issue fixed for us.

So anyway. Thanks for all of the responses. I'm half expecting this issue to come back, but for now this is the best situation we've had over the past 6 days.

Cheers

Dave