Which firewall are you using? Can you telnet from your Zimbra server to port 25 on the server that fails? Post the output again of the following commands:
Code:
cat /etc/hosts
cat /etc/resolv.conf
dig yourdomain mx
dig yourdomain any
host `hostname` <- use backticks not single quotes