The additional details were helpful. From your first post I was thinking that your server was blocking all encrypted e-mails from the outside company. However, it now appears that you are using the certificates in client computers. Now I see why yout IT department thinks it is on their end. It looks like their certificates did not get installed correctly. Missing certificate details could well be the problem. The senders should try to get the the certificate they need to send to you fixed so it contains all necessary data. At this point, I don't know if they are using the same certificate to send to other users, or if they have indovodual certificaets for each sender and receiver pair.