I've seen something similar when going through an old Cisco PIX firewall, but typically it's when sending DATA.
Was the ISP support any help? They may have a more helpful error on their end.
It could also be an antivirus on the remote end.
If sending a message via telnet works and all else fails, you could always try putting Postfix into debug mode for that host:
Postfix Debugging Howto