I have used both of the methods you mentioned, the only real difference being that when using "use lib" I have always used
use lib qw(/a/path /another/path);

The path is showing up in @INC and the files is in the path but PERL chokes on it every time.