You can use rsync to keep a local mirror of the module metafiles only from a CPAN mirror. This takes much less disk space than mirroring the whole CPAN, and if you've downloaded them once you can use rsync to keep it up to date while transferring only the new files on the net. A command like rsync -Rvz "cpan.some.mirror.com::CPAN/modules/by-authors/id/?/??/./*/*.meta" "cpan.some.mirror.com::CPAN/modules/02packages.details.txt" /path/to/local/mirror should work if you change the url to a CPAN mirror close to you.
Once you've got the metafiles and the 02packages.details.txt, you can parse them and search in them. The metafiles contain the dependenct modules of each distribution, and the 02packages.details.txt tells which distributions provide which modules.