In a similar vein to what Fletch suggests, you can re-arrange @INC to have the directory you believe is most likely to contain the module come first. (Perhaps rotate the array?)

Of course, if the Perl ever changes (by way of an update) or the include path is otherwise changed (someone sets PERL5LIB in a shell script somewhere up the chain) then you'll still incur some extra lookups. As long as you don't remove any @INC entries then at worst it will perform similarly to how it does now.