I have a perlwhich script (written in perl, of course), to which you can give a module name, and it will search @INC for a module by that name.
This gives you the path to the library, and if it is installed in your @INC path or not.

I can post it to snippets if you think it would be helpful...

EDIT: Posted here: perlwhich - find which perl module you are using (and more). And some (better?) ones have been posted here: whichpm.

Sample Output:
>~/bin/perlwhich  -m 'Storable'  
/util/lib/perl5.8/lib/5.8.0/alpha-dec_osf -- Storable (2.04) - persist
+ence for Perl data structures
/util/lib/perl5.8/lib/5.8.0 -- Memoize::Storable (0.65) - store Memoiz
+ed data in Storable database
[download]