You'd think they should, but they don't. Try the following:
$ PERL5LIB=/no/such/dir perl -le 'print for @INC' > foo
$ PERL5LIB= perl -le 'use lib "/no/such/dir"; print for @INC' > bar
$ diff -u foo bar--- foo 2009-05-07 16:24:12.000000000 -0700
+++ bar 2009-05-07 16:24:32.000000000 -0700
@@ -1,12 +1,3 @@
-/no/such/dir/5.8.6/x86_64-linux-thread-multi
-/no/such/dir/5.8.6
-/no/such/dir/x86_64-linux-thread-multi
-/no/such/dir/5.8.5
-/no/such/dir/5.8.4
-/no/such/dir/5.8.3
-/no/such/dir/5.8.2
-/no/such/dir/5.8.1
-/no/such/dir/5.8.0
/no/such/dir
/usr/lib64/perl5/5.8.6/x86_64-linux-thread-multi
/usr/lib/perl5/5.8.6
And now we see the difference that
saintmike was talking about. If you put stuff in $ENV{PERL5LIB}, it adds a list of internal hardcoded architecture specific directories to look in
whether or not those directories exist, and regardless of the contents! By contrast use lib adds subdirectories based on a heuristic about their contents.