E-mail servers can be very difficult to manage, and not necessarily because of a problem on your side, it can often be due to aggressive anti-spam measures on other people's e-mail servers.
It appears that Google is very aggressive with rejecting e-mail from servers they suspect of spamming, and I do not blame them — they have to deal with huge amounts of spam.
The problem is, however, as a result of these aggressive anti-spam measures, you can not really send e-mail to Google's servers without risking that your server is blocked. Even legitimate e-mail, such as subscription- or user-creation confirmation mails appears to be a risk; and once you are blocked, there is little help as to what can be done to get yourself unblocked.
This can significantly disrupt both users of Gmail and the user of your e-mail server.
I recently learned my own e-mail server had been blocked, so whenever I try to send an e-mail to gmail I now get a useless error message telling me (erroneously) that my e-mail is "unsolicited mail":
Our system has detected that this message is 550-5.7.1 likely unsolicited mail. To reduce the amount of spam sent to Gmail, 550-5.7.1 this message has been blocked. Please visit 550-5.7.1 https://support.google.com/mail/?p=UnsolicitedMessageError 550 5.7.1 for more information. ... - gsmtp (in reply to end of DATA command)
The cause of the problem
This problem appears to have been caused by a single client website sending out confirmation e-mails for mailing list subscriptions. On this client's website, the subscription form appears to have been targeted by spammers that was constantly subscribing random e-mail addresses.
The offending site was a Drupal-based website with a simplenews module. The problem with simplenews seems to be that it does nothing to verify that the submission is valid. As a minimum, it should at least prevent people from subscribing the same e-mail twice until a confirmation has been received; instead it appears to just repeatedly send the same e-mail over and over whenever someone submits it through the subscription form.
Securing subscription forms is very difficult to do. Even with fail2ban configured correctly, people can oftentimes just use proxy servers to circumvent temporary bans, so this is probably the hardest obstacle I have encountered in my own SMTP adventure.
Gmail is very aggressive in blocking other e-mail servers. It would have been much more reasonable if they added a temporary ban to the offending user; they really should not ban entire servers. In my case, the client was always sending service e-mails from a single address, like firstname.lastname@example.org, so all they needed to do would be to block this sender.
How to solve the problem
You probably just have to fix whatever is causing the problem and wait it out. In my own case I just had to wait a few weeks after I fixed the subscription form that was being attacked by spammers, and after this period, I was again able to send e-mail to gmail addresses.
In the meantime, you can check services such as www.senderscore.org — note that the report is free — they just ask you to sign up. It is a bit annoying you have to sign up imo.
Besides this, there is also postmaster.google.com. The strange thing about Google Postmaster is that there is no data available when you first create your account, it just greats you with the message:
No data to display at present. Please come back later. Postmaster Tools requires your domain to satisfy certain conditions before data is visible for this chart. Refer to the Help page for more details.
I am not sure when it starts showing, but I am still waiting, and it has now been a few weeks after I verified my domains. Since I managed to fix the problem, I am not sure if I want to spend more time trying figure out how to get the postmaster.google.com stuff to work — maybe I just have to wait — not exactly sure what is happening.
When you need to confirm a domain name with google postmaster tools, and if you already got a TXT record in your DNS, you just need separate the declarations with a line break:
"first declaration here" "second declaration here"
Have fun :-D