It looks like gmail has increased it's spam detection furiosity. We have many complaints from customers having their e-mail sent to their servers bouncing back.
Most of the time it was because they didn't set a correct SPF for their domain. It was getting through a week ago (probably to spam box though) but now it is bouncing right away.
It is possible they alsochanged something about the message message-id header checking. We don't have this issue though,
I guess it's because we're using outgoing gateways and it is adding a message-id header if it's missing.
AFAIK message-id can be either generated by the mail client submitting the mail to the server, or if missing the mailserver should add one.
I did a test sending a mail from emClient with SMTP through smartermail and on gmail side the message-id looks like:
<em06326e16-c065-47e8-9fdc-3b3b9aacb8eb@19e41120.com>
Looks to me like emClient add a message-id.
Now if I do the same test with SM webmail the message-id looks like:
<7e838ded6dcc4d47be15b0c0e417759b@mydomain.com>
This one looks generated by SmarterMail (or maybe our gateway, not sure at this point)
On your side, does all messages to gmail get rejected or only some ?
If it's only some messages, is there a pattern that could emerge, like it depends if it's sent with SMTP, webmail, MAPI, EAS ?
Can you send a mail to another non-gmail address to check the message-id in the received message's source ?