Question : Problem sending to some servers from exchange 2003

Exchange 2003 on Server 2k3 standard.  

Mail server and barracuda spam appliance are behind fortinet firewall.  All traffic in and out is good besides a few domains.  One in particular is verizon.  We are not on any blacklist, and I called verizon and verified we are not on their blacklist.

I have MX set to barracuda1.lindentravel.com
A record to barracuda1.lindentravel.com
A record Exchange1.lindentravel.com
PTR for barracuda1.lindentravel.com 38.112.24.155
PTR for exchange1.lindentravel.com 38.112.24.155

Both are inside the firewall with local IP's using that Virtual IP.

When I send to verizon and watch the exchange queue, I see smtp error occured, and nothing else.  

Someone point me in the right direction? DNS comes back good, and I can telnet to 25 to verizons server no problem.  The message seems to go, but I get no bounceback and no notification that it did not reach its recipient.

Thanks to all who might be able to assist!

Answer : Problem sending to some servers from exchange 2003

Are you sending and receiving on the same IP address or different ones?

If different, this could be the cause of the verizon problems.

Change the sending IP to be the same as the receiving IP and test to verizon,