1) Their hosting provider does not provide reverse dns services
Why do you think that is relevant?
It is the only piece of information that I received from the hosting provided that might explain the problem
I've already told you - no.
My bad, I missed that in the previous post
If you post the full actual message you are seeing in the qmail logs someone may be able to help you.
@4000000048d281fd2e9a139c new msg 11780118
@4000000048d281fd2e9a2ef4 info msg 11780118: bytes 1510 from <charlies@poliac.com> qp 25325 uid 453
@4000000048d281fd2f8a99d4 starting delivery 168071: msg 11780118 to remote undisclosed@presym.com
@4000000048d281fd2f8ab914 status: local 0/10 remote 1/20
@4000000048d281fd344779ec delivery 168071: failure: Sorry,_I_couldn't_find_any_host_named_presym.com._(#5.1.2)/
@4000000048d281fd35dc6614 status: local 0/10 remote 0/20
@4000000048d281fd3799f87c bounce msg 11780118 qp 25327
@4000000048d281fd379a13d4 end msg 11780118