Gmail.com detect mail as spam, but the server is not on any BlackList

blacklistemailgmailspam

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: <tomer@megatec.co.il>
250 2.1.0 OK g47si45436208eep.123
rcpt to: <weinberg.tomer@gmail.com>
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?

EDIT:
Added SPF Record to our domain few Days Ago…
Still NO GO 🙁

Best Answer

HELO Mistake

The email is being sent out from

    mail.megatec.co.il. 62.219.123.33

Not

    megatec.co.il. 67.228.132.128

Your helo should be

    helo mail.megatec.co.il

SPF - Not Available

Your SPF is either not update or setup incorrectly. A dns query to varies server fail to retrieve it. Even the SOA(ns1.bezeqint.net) failed.

If TXT is setup correctly, ns1.bezeqint.net should relfect the changes within a few minutes, regardless of TTL.

Google dns

# dig @8.8.8.8 megatec.co.il txt

; <<>> DiG 9.8.1-P1 <<>> @8.8.8.8 megatec.co.il txt ; (1 server found)
;; global options: +cmd ;; Got answer: ;; ->>HEADER<<- opcode: QUERY,
status: NOERROR, id: 42780 ;; flags: qr rd ra; QUERY: 1, ANSWER: 0,
AUTHORITY: 1, ADDITIONAL: 0

;; QUESTION SECTION: ;megatec.co.il.            IN  TXT

;; AUTHORITY SECTION: megatec.co.il.        1800    IN  SOA ns1.bezeqint.net.
hostmaster.bezeqint.net. 2010111500 10800 900 604800 86400

;; Query time: 307 msec ;; SERVER: 8.8.8.8#53(8.8.8.8) ;; WHEN: Mon
Dec 24 13:18:09 2012 ;; MSG SIZE  rcvd: 94

OpenDNS

# dig @4.2.2.2  megatec.co.il txt

; <<>> DiG 9.8.1-P1 <<>> @4.2.2.2 megatec.co.il txt
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 21588
;; flags: qr rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0

;; QUESTION SECTION:
;megatec.co.il.         IN  TXT

;; AUTHORITY SECTION:
megatec.co.il.      3600    IN  SOA ns1.bezeqint.net. hostmaster.bezeqint.net. 2010111500 10800 900 604800 86400

;; Query time: 338 msec
;; SERVER: 4.2.2.2#53(4.2.2.2)
;; WHEN: Mon Dec 24 13:21:37 2012
;; MSG SIZE  rcvd: 94

ns1.bezeqint.net

# dig @ns1.bezeqint.net megatec.co.il txt

; <<>> DiG 9.8.1-P1 <<>> @ns1.bezeqint.net megatec.co.il txt
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 11214
;; flags: qr aa rd; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0
;; WARNING: recursion requested but not available

;; QUESTION SECTION:
;megatec.co.il.         IN  TXT

;; AUTHORITY SECTION:
megatec.co.il.      3600    IN  SOA ns1.bezeqint.net. hostmaster.bezeqint.net. 2010111500 10800 900 604800 86400

;; Query time: 150 msec
;; SERVER: 192.115.106.10#53(192.115.106.10)
;; WHEN: Mon Dec 24 13:25:25 2012
;; MSG SIZE  rcvd: 94