This sounds similar to some things I have wrestled with in the past but I looked over some of my notes and could not find the exact reference due to having way too many notes and also trying both PGP and GPG, it's been several months.. Anyway one thing you may want to try is consider that the bug message may be wrong, it is not having trouble understanding the recipient but rather the sender. I seem to remember something like that..

Also it may be that if this happens to be on a shared server (if so be real careful with your secrets..) it may be using a different ring.

In my case I also had trouble with tons of dependencies in other modules, I had an old perl. I ended up rolling my own module using Storable, IO::Handle, and GnuPG::Interface, and Class::MethodMaker. Perl libs were built with a local prefix.

First I made a keyring on the command line and imported a public key into it. The key has to be trusted, which can be done without any secret keys being installed by editting .gnupg/options (reading the comments is essential). The encrypted text is ascii armored and can be copied or downloaded for decryption with a GPG client like WinPT / GPG.

Note it is not very secure to encrypt things on a shared server, however since it was not an extremely heavy situation I did a couple things like chmod my own gpg binary -rwsr-xr-x to attempt to secure memory, plus filling strings with zeroes before they went out of scope to try to keep data from remaining in the swap partition.

Anyway I'm guessing you have a much better environment available to you. It does sound however that PGP is fighting you because it thinks you have a different identity than you really do; this is the main reason I have found PGP/GPG to fight when it works on the command line. If you can figure out who it thinks you are (very hard I think) you are there.