You could try a few things:
Use system to run Perl -v and use that to figure out where Perl's libraries are. You could then walk up the library locations to test for a bin directory. For instance ActiveState Perl has a pretty standard installation, I'm sure other Perls do as well;
Use a standardized installation for Perl on all recipient machines - that way you known where it is always going to be. Make sure perl is part of your PATH variables. For instance if you run set through a system or cmd call, you can grep for PATH and then grep for the instance of your Perl installation. That's something you may have to organize with your IT department;
Use a packaging program to bundle up Perl with the associated program and modules you need to run your stuff. I use ActiveState's PDK PerlApp for this. Its pretty robust and I know I can create something that other IT groups can install on a large number of computers.
Of course if you can run the app through the web you can avoid installation issues...
Hope that helps.
MadraghRua
yet another biologist hacking perl....