We have recently become aware of the fact that GMail is likely to consider e-mails without a message id in the header as spam. It appears that it is fairly common practise for the receiving SMTP server to add the id if it is missing, but our hosting provider don't and they are not inclined to turn the setting on.

I know it is possible to create custom workflows to handle this, but that means we will have to maintain our own solution and our customers will see "Send email" and "Send email with message id" in the workflow dropdown.

Will you consider adding a few lines of code that solves this problem?

From what I can tell something like this would do it:

string fromEmail = umbraco.UmbracoSettings.NotificationEmailSender;
string senderDomain = fromEmail.Substring(fromEmail.LastIndexOf('@'));
m.Headers.Add("Message-Id", "<" + Guid.NewGuid().ToString() + senderDomain + ">");