First thing would be to set back everything as it was as you will need to perform DNS lookups if you are not relaying through an upstream SMTP server.
Second you should ask the sender to get their IT department to fix DNS
Third go to the Admin GUI and under Global Configuration -> MTA -> Disable the DNS checks for Unknown Hostname.
You will need to restart the MTA so from a command prompt
It would also be useful to post which checks you have enabled
su - zimbra
zmmtactl stop ; zmmtactl start
zmprov gacf zimbraMtaRestriction