I have an issue with Google. (GMail to be exact)

About 1 month ago, we had a security breach, and mail was relayed through our servers. we got listed in almost ALL Black-Lists :(

we fixed the problem, and requested removal from Black-lists, which was granted easily.

currently (over 3 weeks), we are not sending any spam anymore.
furthermore, we got clear from all the Black-lists (MxToolBox Black-List Search Result)

But, GMail still refuse to get Anything from the server, stating '550 Spam'.

Following, Telnet attempt to send to gmail:

220 mx.google.com ESMTP g47si45436208eep.123
helo megatec.co.il
250 mx.google.com at your service
mail from: <[email protected]>
250 2.1.0 OK g47si45436208eep.123
rcpt to: <[email protected]>
250 2.1.5 OK g47si45436208eep.123
Data
354  Go ahead g47si45436208eep.123
Test123
.
550-5.7.1 [62.219.123.33      11] 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 http://support.google.com/mail/bin/answer.py?hl=en&answer=188131 for
550 5.7.1 more information. g47si45436208eep.123

Connection to host lost.

i tried filling the form @ Gmail - Report Delivery Problem
i also tried reaching Google by phone, but the message was to go to the Link mentioned above.

I Checked ReverseDNS and is ok...
We dont have TLS, but that shouldn't be a problem, shouldn't it?

Note: we are not a Bulk sender.

Anyone has an idea? what can be blocking our IP?

Anyone know whom can be contacted in order to resolve this BL listing?