User "asaveljevs" from the zabbix forums suggested I post this issue here.

Basically, the zabbix emailer doesn't handle multiple 220 OK lines coming back from a mail server. As a part of legal requirements, some organizations are required to print multiple lines with legal or other warnings in their 220 OK messages. Since zabbix expects only one line, it sends its HELO, but the receive buffer will still contain the 2nd, 3rd, etc. 220 lines. Since zabbix expects 250, the mailer sender stops even though it could have successfully sent the mail.

(From my original forum post)
http://canonic.net/txt/articles/28/zabbix-183-wrong-answer-on-helo-

I don't know if this is correct under the RFC SMTP specification, but some smtp server administrators print out multiple 220 lines with additional information about their mail server. Zabbix handles this case poorly because the code in email.c only expects one "220" line after connecting, sends its HELO, and then reads the next line in the buffer which is another 220 line. Since zabbix expects "250" it fails to send the email message, even though the server is operational. The modification at the above link is one way around this limitation.