If you don't have a rDNS entry then worth getting one sorted out.
The reverse DNS (rDNS \ PTR) record is configured by the people who issued your IP address in most instances (so your ISP).
Below are two articles which explain the general requirements for reverse dns (rDNS\PTR) records for your IP address.
I try to adhere to the following when setting up a rDNS (PTR) record:
Be a Fully Qualified Domain Name (FQDN) such as server.domain.com (not just 'domain.com' or 'server').
Should not contain 'in-addr-arpa' and should not include words like pool or dyn etc.
Should match what you use in your SMTP HELO\EHLO hostname if possible.
For neatness and as a good rule of thumb, if your incoming mail is delivered to the same server that you use for Outgoing you should make sure all the following FQDN's match:
MX record
rDNS (PTR) record
SMTP EHLO hostname
http://www.simpledns.com/kb.aspx?kbid=1052 http://postmaster.aol.com/info/rdns.html http://www.amset.info/exchange/dnsconfig.asp (Courtesy of EE member Mestha)
As for the actual problem at hand, can you use telnet from the server to these destinations from the server? Are there any firewalls blocking port 25?
Shaun