Recently my VPS provider changed the IP address for the server. On top of updating the hosts file, you also need to update the IP address used for the MTA.

In the Zimbra Web Admin Console, Configure -> Servers -> Click on the server in the right pane -> MTA -> MTA Trusted Networks