Your dig commands are incorrect, they should be for the domain name not the FQDN of your server i.e.
Code:
dig bcrockford.com any
dig bcrockford.com mx
and the host command should be exactly as I asked you for in the lost post:
Code:
host `hostname` <-- do not modify or add anything to that command use it as-is
Are you using any of the SMTP proxy or inspection on the EFW? Is the EFW just set for the RED interface or GREEN as well?
I also asked if you can telnet from the Zimbra server to port 25 on the mail server of a failing host?