We work with a major parcel delivery company that as of 10/8/2012 has been unable to email us from their customer service software. All other emails from individuals in the company come through just fine.

I finally found it in the logs where the messages are at least attempting to be delivered, but are being rejected by our server:

5.7.1 rejected due to DKIM ADSP evaluation;

Relevant log lines:
Code:
Oct 25 15:04:11 mail2 postfix/smtpd[28320]: connect from mt01.cimondemand.com[67.217.236.34]
Oct 25 15:04:11 mail2 postfix/smtpd[28320]: E537C9DA2AC: client=mt01.cimondemand.com[67.217.236.34]
Oct 25 15:04:12 mail2 postfix/cleanup[2978]: E537C9DA2AC: message-id=<20121025150411.E537C9DA2AC@mail.ourdomain.co>
Oct 25 15:04:12 mail2 dkim-filter[20376]: E537C9DA2AC rejected per sender domain policy
Oct 25 15:04:12 mail2 postfix/cleanup[2978]: E537C9DA2AC: milter-reject: END-OF-MESSAGE from mt01.cimondemand.com[67.217.236.34]: 5.7.1 rejected due to DKIM ADSP evaluation; from=<team@largepacageshippingcomapny.com> to=<cole@ourdomain.com> proto=ESMTP helo=<mt01.cimondemand.com>
Oct 25 15:04:12 mail2 postfix/smtpd[28320]: disconnect from mt01.cimondemand.com[67.217.236.34]
Before I tell them to get their stuff working, is this problem on our end, or do they just have invalid DKIM keys set up in their system?