For my work application, the modules are installed into an installation-specific directory (which is never in perl's lib hierarchy). They are all named with an application prefix ("NVC::" in this case), but that's more to avoid confusion in coding than confusion on the filesystem.
Scripts tend to have an early:
use lib 'lib'; # fixup on install
which is fixed up at installation to point to the installation's lib directory. (If you run an uninstalled script directly from the CVS checkout directory the unmodified line will also do the right thing, as long as you are in the top-level directory to start with.)
This system works very cleanly for us, and we have some 40 or so installations of the application (scattered across various revisions of the code) all happily coexisting on a single machine.