It turns out that for the mail Server (MS Exchange) in question I needed to use this method:
Writing an encrypted mail via Exchange Web Services
var item = new EmailMessage(service);
item.MimeContent = new MimeContent(Encoding.ASCII.HeaderName, content);
// Set recipient infos, etc.
item.Send();
It seems to be because of the encrypyed MIME attachment. Using the standard To, From, Subject properties of the Microsoft.Exchange.WebServices.Data.EmailMessage class does not work correctly.
Although it does work as expected when the mail server was SmarterMail.
SmarterMail 9.x is one of the only mail servers (including Microsoft Exchange) to support Exchange Web Services (EWS). (from http://blogs.smartertools.com/tag/exchange-web-services/)
Anyone know why SmarterMail would behave differently to MS Exchange?