Endpoint Encryption

Our company sells products to the Federal Government and recieves their orders via email (Microsoft Outlook). The emails are in code and we use PGP to decrypt them. About every 4 or 5 emails, we get some sort of error message and it will not work (Error: No PGP Content). In the past I have had my contact at the Feds fix the problem. She usually had me delete me key, create a new one and email to her. Problem fixed. Now she has left that position and my new contact has no experience with PGP. When I got the error again, I deleting my key and sent the new one to my new contact. Now when I try to open the message the error I receive reads, "Missing one or more decryption keys." I have a feeling that my new contact is doing something wrong on their end when I send the new key. Any ideas on how I can fix this? I am going to have some unhappy customers very soon.

PS. Apparently I have a version of PGP that DOES NOT allow tech support. We bought this product and when I need help I have to spend $180 to get it fixed. Wow.

Thanks in advance for any help with this. 

The error message is indicating that the encryption is not to your public key.  I don't know what they are doing on their end to require a regular key update from you - they might possibly be giving it a time limited signature.  I'd suggest never actually deleting your key, but instead disabling it when you create a new one - they might possibly be encrypting to one of your old keys that you cannot now decrypt since you deleted the private key.  You might want to ask her to delete any existing key she has for your email address, send her your new key, and explain to her that she needs to sign your new key so that she can encrypt to it.  However, it seems that since this is a government office, that there would be someone doing this for her, perhaps at the server level; if so, it might be better for you to interact with that person to resolve this.