This is a long shot, but is it possible that one of the earlier dirs in @INC has permissions that prevent perl from looking in it and is causing perl to terminate the search early? That "permission denied" message might make that feasible.
Edit: Another thought, do you know for sure what effective uid/gid perl is running under? Is it possible the SUID bit is set? Like I said, these are long shots at best.
It helps to remember that the primary goal is to drain the swamp even when you are hip-deep in alligators.