Quote Originally Posted by MMock View Post
(The x's were more realistic values in the real error, not sure if I'd be revealing anything I shouldn't if I didn't x-them out).
Nah they would just be the SMTP response codes, I'm guessing it started with a 5?

Anyway, I would do a blacklist check on your external IP address / DNS address and see if you are on any well known black lists - this is a fairly decent free one: http://www.mxtoolbox.com/blacklists.aspx
If that all comes back clean then I would just try to contact the company you are sending the email to and ask them to add your domain to their white list / safe senders list.