I am no longer using the MailMessage class, because I could not get it working. Instead I am using EWS managed api like this:
var mail = new EmailMessage(_service);
mail.Subject = filename;
mail.MimeContent = new MimeContent("us-ascii", Encoding.ASCII.GetBytes(messageContentWithHeaders));
mail.SendAndSaveCopy();