If these are Unix machines, then you might have more luck with #!/usr/bin/env perl which will scan the systemwide PATH. "Might", because env has occasionally been known to reside in different directories as well..

Makeshifts last the longest.