Well, if this is true, your perl is broken :) Or your script resets @INC. Or your script runs in taint mode (-T). Or you showed the wrong error message in your OP.
Items in PERL5LIB should otherwise always appear in the reported @INC:
$ PERL5LIB=/foo/bar perl -MNot::Exist -e1
Can't locate Not/Exist.pm in @INC (@INC contains: /foo/bar /etc/perl /
+usr/local/lib/perl/5.14.2 /usr/local/share/perl/5.14.2 /usr/lib/perl5
+ /usr/share/perl5 /usr/lib/perl/5.14 /usr/share/perl/5.14 /usr/local/
+lib/site_perl .).
BEGIN failed--compilation aborted.
As you can see, /foo/bar has been added to @INC.