Just out of curiosity... you could compare the strace output you're getting with PERL5LIB against the corresponding attempt with "use lib ...". If the one works and the other doesn't, there presumably is some difference in which places are being searched...

$ strace -efile perl -MSome::Module -e1 2>&1 | grep Module
[download]

(where Some::Module of course is a module that exhibits the difference)