None of the supported CPAN communication methods (LWP, ftp, ncftp,
lynx, etc) would work behind my proxy server, regardless of how many
parameters or configuration files or environment variables I fooled
with. I Googled usenet, and found lots of suggestions, but nothing
helped.

But I was able to get it to work using an excellent, open-source
program called cURL. cURL is similar to (but much more powerful than)
wget. cURL is bundled with many Linux distros, or you can get it from
http://curl.haxx.se. I'm using AIX and installed cURL from an IBM RPM
(http://www-1.ibm.com/servers/aix/products/aixos/linux/download.html)

I have NO problems getting cURL to work with my authenticating proxy
server. To simplify the process, I created a cURL resource file,
$HOME/.curlrc (chmod 600) which contains these two parameters:
   -x proxy.whatever.com:8080
   -U myuserid:mypassword
The "-x" parameter specifies the hostname and port of the proxy
server, the "-U" (uppercase) is my proxy server userID and password.
cURL finds and uses this resource file by default.

But how do I get the CPAN module to use cURL? Simple. I lie to it. In
my CPAN/Config.pm file (in @INC) I edit the value of 'wget' thus:

   'wget' => q[/usr/bin/curl],

To prevent the use of other external methods that won't work, I pass
null values to these CPAN/Config.pm keys:

  'lynx'     => q[],
  'ftp'      => q[],
  'ncftp'    => q[],
  'ncftpget' => q[],

Don't bother defining anything for the *proxy* keys - leave them null.
cURL will do the proxy negotiation using the $HOME/.curlrc parameters.

Now CPAN thinks that my cURL is my wget program (and it thinks wget -
er, cURL - is the only external method available). But I need to tweak
the CPAN module itself to make this work (and, if you ever update the
CPAN module, you will need to tweak it again). Edit CPAN.pm (in @INC)
and find the bit of code that says:

          } elsif ($f eq "wget"){
              $src_switch = " -O -";
          }

Change the scalar assignment to:

          $src_switch = " -- ";   #was: $src_switch = " -O -";

It should work now, but you will get warning messages (and delays) as
CPAN tries (and fails) to use the built-in communication methods (LWP
and Net::FTP) first. So you might want to tweak your CPAN.pm module a
little further.

To prevent the CPAN module from trying LWP and Net::FTP first, I also
made a small change to the "has_usable" subroutine. Namely, I added a
preemptive false return, like this:

sub has_usable {
    my($self,$mod,$message) = @_;
    return $HAS_USABLE->{$mod} = 0;  #force it reject LWP and Net::FTP
    ...

And to avoid seeing pesky (and prolific) LWP warning messages, I
commented out the line that says
    #$CPAN::Frontend->myprint("LWP not available\n");

Now I can use -MCPAN to do module installs behind my authenticating
HTTP proxy server. It's quick and clean to use (even if it's a
kludge). Maybe it might help you if you're in a similar environment.