Just try to telnet your SMTP server and to type this address manually to see if it will return the same error
so,
telnet you_smtp_server 25 (25 is the default port number, otherwise check /etc/services to make sure that this is the right port)
once connected
<cr> stands for carriage return
HELO <cr>
MAIL FROM:<your@email><cr>
RCPT TO:<your_tricky_address_causing_problems><cr>
DATA<cr>
Type any data and finish by a single dot "."
quit
You'll see whether you receive the same error, if not, it means that your PHP script sends some nasty characters