[xtiansimon]

Just to be clear, your comments are refering to problems with Gmail's Spam filtering. Isn't that a different issue than what the OP is saying--that his mailserver is being blocked? In other words, emails from his mail server wouldn't even make it to Spam folder.

[fgonzag]

Gmail spam filtering and it's mail server are two sides of the same coin. The mail server itself is blocking believed spam messages as a first layer, then the spam filter acts a second layer that marks messages as spam. I guess they don't want to save messages that they are completely sure are spam, the problem seems to be their false positive rate or simply their approach against small operators.