hi..i dont know if you have connetivity problem or PTR..
do you have SNAT setup behind firewall? because if you dont then you firewall IP is what is going out and you may have PTR to your mail server ip.
check that and see what public IP is showing up in the headers to the ISP were you can get email.
if its your firewall IP then fix your PTR and check at the following link if your IP resolves.
http://postmaster.aol.com/tools/rdns.html
all the above is only for RDNS test/fix..if you have any other prob then please post the maillogs.
Raj