Have a look at the 02packages.details.txt.gz and 03modlist.data.gz files in .cpan/sources/modules. I think they contain "complete" lists of packages and modules available for download.

update: You might find PackageDetails helpful for dealing with the packages file.

update: The modules list may be registered modules only.