Problem using public key for s/mime

I have tried using s/mime encrytpion for the first time. I have created 3 different accounts using the same CA on 3 different devices. All three can communicate with each other using the s/mine encryption. I used multiple methods - sending a signed email first and then encrypted+signed, creating a .pem file with public key - importing it in Manage certificates/people and sending an encrypted+signed email. Sending an encrypted email from-to the same address also works. What I can't seem to be able to do is use any other public keys. I have a list of companies and their keys, but whether I use a file downloaded from their site or copy the key to txt and then make a .pem file out of it, as I did with my addresses, I can't send an email that is both encrypted and signed. I get "end-to-end encryption requires resolving certificate issues for ..." and the recipient status "not found". They specifically don't want to send a signature first and then encrypted+signed, and I am stuck trying to figure out what I am doing wrong. Any help is greatly appreciated.