In the last 24 hours I have been fighting a strange spam related problem with GMail. The email for some of my customer's domains are sent to my main mail server, which decides per user account which actions to take further. Some email is forwarded further to other mail servers, other email is stored on the server until a user reads it with a webmail application or retrieves it via a POP3 or IMAP connection.
Yesterday email for one of the users started bouncing during the forward to his GMail account. GMail didn't accept any messages anymore from my email server to his account and refused them with a 554 Message refused. error. No further explanation of the error like full mailbox or otherwise; just refused. The strange thing was, all email sent from my central mail server to accounts of other users on GMail was accepted as usual, and also email coming from a different server to the problematic GMail account was accepted without problems.
I have scratched my head several times over this and the only conclusion which seemed acceptable was that GMail didn't like the combination of the IP address of my sending SMTP server, and the account name on the GMail side. I therefore asked this user if he had marked some messages in the recent past as SPAM, and he responded that he had marked one message forwarded through my email server as being spam. That message had been marked yesterday, just before the message forwarding stopped working. The apparent result of marking this single message as spam was that all email sent to his GMail account via my server was now regarded as spam and rejected at the door. Although this forward had been in place for several months and he receives an average of 10 messages a day over this forward channel, one message marked as spam seemed to be enough to block his mail forwarding stream completely.
It is nice to know that GMail uses spam fighting techniques, but marking a sending SMTP server as a notorious spammer if only one out of several hundreds of messages from that SMTP server is marked as spam seems a bit strange for me.
We have now solved this problem permanently by storing the email on my server instead of forwarding it. GMail polls every few minutes over encrypted POP3 if new messages are available and downloads them.
If you are using message forwarding to GMail accounts you may want to check your logfiles for bounced mails and if necessary also change to a POP3 configuration.