Have you tried setting the Public Service Hostname in the Admin UI? You could try exporting the mailbox and then re-importing it into a new account and see if that has the same problem.
Are you sure your DNS etc. is all OK? Just to check, post the output of the following commands run on the Zimbra server:
Is this a single server and do you have the proxy installed, by any chance?
dig yourdomain.com any
dig yourdomain.com mx
host `hostname` <-- use that exact command with backticks not single quotes