This has been a head-scratching issue for a couple of weeks. We had some issues with our mail server where a user's account was compromised and spam was being sent. Google's Gmail eventually blocked all emails coming from our mail server's IP, no matter the domain name.We fixed the issue and no more spam was sent. However, Gmail kept blocking us even two weeks after. Inspecting our logs, we noticed the returned Gmail SMTP 421-4.7.0 error "Our system has detected an unusual rate of unsolicited mail originating from your IP address". Reading more about the Bulk Senders Guidelines, we noticed this part: "Messages must have a valid 'Message-ID:' header field". It turns out messages sent by our custom .Net backend did not include a Message-ID.Once we enabled "Header fixing" on our mail server by automatically adding missing Message-ID, new messages sent to Gmail started to go through again. Hope this can help you out in solving your Gmail delivery issues.
