I had something similar to your situation but i finally was able to get rid blocked ISP host from my e-mail route. I bought a co-location service and set up a proxy host on Debian lenny with ASSP and proxy postfix for non-local email delivery.
Everything is working fine except that i still need to set-up cname and revDNS for my proxy email gateway.
The strangest thing ever i noticed the host is unable to send email to scglobal.net.
The error is :
Nov 1 13:49:58 proxy postfix/error: 0AD31105C74A: to=<email@example.com>, relay=none, delay=183349, delays=183349/0.01/0/0, dsn=4.3.0, status=deferred (mail transport unavailable)
No idea how to resolve this problem. Everywhere else emails are send with OK status. Didn`t check the gmail.com or yahoo.com but im my interest now is the sbcglobal.net because ppl that use my server want to send the emails there . Nothing seems to resolve it... I tried to set up transport manually but without any sucess.
Somebody know how to resolve my problem ?