Here's a problem with a company's zimbra server. They can't send any mails from their domain to gmail accounts.

When attempting to send to my gmail account they receive the following mail back:
This is the mail system at host

I'm sorry to have to inform you that your message could not
be delivered to one or more recipients. It's attached below.

For further assistance, please send mail to postmaster.

If you do so, please include this problem report. You can
delete your own text from the attached returned message.

The mail system

<>: host[]
said: 550-5.7.1 [ 1] Our system has detected an
unusual rate of 550-5.7.1 unsolicited mail originating from your IP
address. To protect our 550-5.7.1 users from spam, mail sent from your IP
address has been blocked. 550-5.7.1 Please visit
Bulk Senders Guidelines - Gmail Help to review 550 5.7.1 our Bulk
Email Senders Guidelines. g67si16254245yhk.95 (in reply to end of DATA

What's more, when checking into /var/log/zimbra.log I found these entries there:
Aug 27 06:53:18 maila amavis[10627]: (10627-03) Checking: p5bnAWbPdCAz [] <> -> <>
Aug 27 06:53:18 maila amavis[10627]: (10627-03) Open relay? Nonlocal recips but not originating:

where would be my gmail account and is the mail account used to send test emails to my account.

I also used to test if their mail server is an open relay, here is the result:
[Method 18]
<<< 220 ESMTP Postfix
>>> HELO
<<< 250
>>> MAIL FROM: <antispam@[]>
<<< 250 2.1.0 Ok
>>> RCPT TO: <>
<<< 504 5.5.2 <>: Recipient address rejected: need fully-qualified address
>>> QUIT
<<< 221 2.0.0 Bye
All tested completed! No relays accepted by remote host!

It has obviously passed this test, so would any of you help me? Why this company can't send mails to gmail accounts? I'm kind of new in this whole zimbra world so if here's not all the information needed to help me please let me know.