It was a Zencart thing
Thanks for your reply Steve. Eventually I tracked down the problem. We use OSTicket to help manage the email from an online shop using Zencart.
Zencart has some built in logic to stop mail it forwards from the site being treated as spam. However this crafting of the email headers caused the problems we experienced.
For anyone experiencing this problem, you need to go to the zencart admin area, and from the configuration->email options page, set "Emails must send from own domain" to FALSE.
I hope it saves you a bunch of time....