warning: no MX host for <domain>.com has a valid address record

This happens on all outgoing mail attempts including gmail, hotmail, etc...

Upgraded zimbra (zcs-6.0.7_GA_2473) last weekend, but this issue seemed to have started today?

Any ideas?