Is the name your server reports in the HELO registered as an MX record for your domain? It could be a spam filtering thing. You server reports its name as 'a.yourdomain.com', but the other end sees the only MX record is for 'b.yourdomain.com' and assumes you are spoofing a name.
Do you get this problem for every server or just that one?