I had the same problem with my server
server is in "server only" mode and act as mail server + ocs server
due ISP restriction I need to use only one IP and I need also several VPN tunnels between branches which was initially implemented with ZyXEL ZyWALL series routers and I have secondary provider for backup of internet connection ....
because of all of this the server works behind of an ZyWALL 35 UTM [firmware version V4.03(WZ.0) | 11/07/2007]
initially the mail server wasn't able to send directly the emails to other servers
everything was strange
after a week of work around I found for moment the solution to delegate mail sending to other email server (which I administrate) with user/pass login (delegate to ISP SMTP server)
recently I discovered that error on the server :
"deferral: CNAME_lookup_failed_temporarily._(#4.4.3)/"
and I realised that the problem came from DNS
initially I used the ZyWALL as DNS relay (there I can set more than 1 or 2 DNS servers - right now I have 6, and also I have several "internal zones" implemented for users already in VPN area)
after I changed the DNS in SME server with one of my ISP emails start to be sent directly without any problem
and the error disappeared from logs
I think you can use one of this routers to simulate the problem