Postfix seems to be consistently rejecting mails from few servers though PTR lookup for those domains is successful. Please see log below. I have run out of ideas on what we can do to get this working. I am sure the issue is not with the sending server as they do not have errors sending to other domains.
Oct 26 09:08:32 mail postfix/smtpd[16158]: NOQUEUE: reject: RCPT from
unknown[XX.XX.XX.XX]: 450 4.7.1 Client host rejected: cannot find your hostname,
[XX.XX.XX.XX]; from=<abc@somedomain.com> to=<xyz@mydomain.com> proto=ESMTP
helo=<somedomain.com>
[root@mail log]# dig -x XX.XX.XX.XX
; <<>> DiG 9.8.2rc1-RedHat-9.8.2-0.23.rc1.el6_5.1 <<>> -x XX.XX.XX.XX
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 26837
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 6, ADDITIONAL: 6
;; QUESTION SECTION:
;XX.XX.XX.XX.in-addr.arpa. IN PTR
;; ANSWER SECTION:
XX.XX.XX.XX.in-addr.arpa. 7813 IN PTR somedomain.com.
;; Query time: 417 msec
;; SERVER: 8.8.8.8#53(8.8.8.8)
;; WHEN: Sun Oct 26 09:24:25 2014
;; MSG SIZE rcvd: 66
Best Answer
Can't 100% answer since you anonamized the data, but Postfix is looking for the PTR and A records to match, as well as the hostname the mail server is claiming to be which looks to be "somedomain.com" from the HELO command in your obfuscated log message.
These are controlled by:
Postfix Config Params http://www.postfix.org/postconf.5.html