This maybe an issue with their system in that it doesn't understand the ESMTP commands
Try and change your smtp connector definition in your exchange
- Start the System Manegr
- Locate and right click the SMTP connector
- Choose properties
- In the properties go to the register Enhanced
- Activate the option "HELO instead of EHLO"
taken from http://www.winserverkb.com/Uwe/Forum.aspx/exchange-admin/24373/smtp-500-5-3-3