I was wondering what happened three weeks ago myself. Did the cert expire?

Do you have an email firewall on your Exchange Server? If the firewall cannot scan the attachments, it will usually strip them off (depending on how it's configured). See if white listing their domain in the firewall helps.

Do you have another email address they could send the encrypted attachments to? Hotmail, Yahoo, etc?

TB