Ok, I finally got in - they had me locked out all day, and with work 3200km away, I couldn't just walk over and smack someone upside the head.

I have an auto-install script which is not CPAN. I check our tarballs in to our version control system as-is, complete with licenses, etc., exactly as the module authors have given to CPAN. I just download and checkin. The auto-install script then does a few things:

1. Sets PERL_MM_USE_DEFAULT to 1 and PERL5LIB to "$install_base/lib" - in your case, $install_base is /home/mysite/perl-lib, thus PERL5LIB will need to be /home/mysite/perl-lib/lib. (I actually use File::Spec so that this may actually work on Windows, but that's not relevant, so I'll skip any other such portability issues.)
2. Untars all the tarballs.
3. Finds any that don't have any unmet dependancies. Installs them.
   • Runs "$^X -I$install_base/lib Makefile.PL LIB=$install_base/lib PREFIX=$install_base". Looking at that now, I don't think the -I$install_base/lib part is required since it's already in PERL5LIB.
   • Runs "make install" (I don't bother with the tests - those are run manually by me before I check in)
   Repeat this step until all tarballs are installed (since now some of the dependancies that were unmet in the previous run may now be met).

So it looks to me that I found some reason to set both PREFIX and LIB when creating the Makefile. So perhaps you should set both. Note that LIB is set to $PREFIX/lib, which makes things really straight-forward.

Good luck!