it would be necessary to perform a find on all directories
I don't think that is neccessary. perllocal.pod lives in @INC, and when you install modules (with ExtUtils::MakeMaker), perllocal.pod gets updated, and the directory mtime gets updated.
Since Module::Build doesn't update perllocal (yet), and neither do ppm or apt-get..., after installing a module an admin might touch @INC
$atime = $mtime = time;
utime $atime, $mtime, @INC;
Additional directories to check might be
perl -V:installbin -V:installscript -V:installsitebin