Either, A) Two vendors mistakenly encrypted messages to the wrong key B) You sent the wrong public key (ie, someone else's public key in your key ring) to both of them C) Somehow your private key was deleted. Following my tutorial, can you make a backup of your private key? Does the key ID match the key that they are encrypting their messages with? Does it match another public key in your key ring? Edit: Hang on, I just caught this: If you encrypt a message with someone else's public key, only they can decrypt it with their private key. (That's why it's a good idea to encrypt it to the recipient and yourself) What you describe in the second paragraph is not the same thing that you describe in the first paragraph.