Look in the deferred queue in the Admin UI and see if the message is there. Do you have any filters enabled that may be moving or, more disastrously, deleting the messages? Post the output from the log files that show the message is being delivered correctly (and some lines before and efter the event).
Originally Posted by iwhite
Just for confirmation, post the output of the following commands (run on the zimbra server):
dig yourdomain.com any
dig yourdomain.com mx
host `hostname` <- use that exact command with backticks not single quotes