Hoople - 12:06 am on Jul 20, 2010 (gmt 0)
OK, your testing has proved your sending IP reputation is clean. Have you verified the IP you tested is the one outside domains see? Some firewalls NAT the DMZ IP that Exchange may be on, even if a public range! Said differently: sending IP = A record of highest priority MX record?
The next steps are to determine which part of the normal mailflow is triggering the error.
From the default console of the mail server establish a telnet session to the remote host and send a test message to a cooperative human at the affected domain. In the data segment you may have to add a date: as a few hosts may require it (some require more client added fields). See [support.microsoft.com ] Many times verbose errors seen here (in a telnet session) are summarized or otherwise morphed when returned via an email server to the sender. DNS configuration problems may be stated more verbosely here too. You might get lucky and get a policy URL giving you steps to unblock! If OK, move to next paragraph.
On a client PC within Outlook set the default message format to HTML. Create a test message to the domain. NO ATTACHMENTS! Does it go through? Some domains block HTML and want only plain text. If NOT OK, move to next paragraph.
If they reject the HTML message do the following. Add a Personal Address Book to Outlook and create and entry for the domain. In the test PAB entry Locate and check the option to send in plain text only. Restart Outlook and send a test message to the domain: open a blank message. Click the To: button and in the pulldown select the Personal Address Book. Click that domain's test PAB entry to add it to the message. DO NOT just retype the SMTP address in the To: box as Outlook will send the default (HTML) then.
If the message goes through you will have to either pursue getting whitelisted for HTML or include links to an external filesharing service. Some domains reject HTML messages created by application because they have no plain text part included (they insist on BOTH being present).
BTW if someone onsite at this customer suggests using a Outlook/AD Contact instead tell them that a contact has no plain text only option.