Lazarui:mattwnz:Ragnor: Sorry to ask the obvious question but does your clients email server has spf, sender id and reverse dns setup?
Also I don't see any quicktime on https://support.msn.com/eform.aspx?productKey=edfsmsbl2&ct=eformts - the capatcha is straight html inputs/images?
Yes, not having reverse DNS can often cause that to happen. The OP hasn't said . If they provided the IP of the problem mailserver it could help.
First post op has noted this:
My client:
Runs their own mail server (server01.heatstore.co.nz )
Has a RIP, PTRs etc to server01.heatstore.co.nz
Has legetimate SPF records
Has a fixed / Static IP address for the last 6 years or so
Has no black listings anywhere
Is not selling viagara etc - they sell peeltt fires, wood fires etc.
Is not virused
Is not running an open spam relay.
Server resolved to: 119.224.53.23
From what I can tell it looks fine, but meh not a expert with domains and mail servers.
Not sure if it is a blacklist, but it gives and error for
Reported by ns3.discountdomains.co.nz on 7/7/2013 at 10:18:05 PM (UTC -5),