First thing first, while configuring the zimbra it will take the hostname.domain as domain name i.e. hostname was mail.foo.com and domainname should be foo.com but zimbra default configuration was to be configure with the mail.foo.com.
Second why the entry
www.xxx.yyy.zzz foo.com is required in the /etc/hosts.
Entry should be some thing like "www.xxx.yyy.zzz mail.foo.com mail "
Various options to make things work for you.
Create domain foo.com as told by other guys and make the MX for foo.com, create all the account you require under foo.com. Data can be migrated from old account to the new one.
Another option can be to rerun the configuration script, don't really know the exact location.
How come to can have the error when you did """Tried creating a virtual server in Zimbra, but no luck. When we try to save an account @foo.com Zimbra returns "The specified domain does not exist""".
Did you mean to host the domain foo.com when you tried virtual host?
Regards
Adeel