You don't need to leave users puzzled. You can simply put the CPAN modules in with your build environment, and have make files install them. That's what I do at $work (see IT department reluctance in my original node). Our make files run a script that goes and untars the modules and runs the install process. If they're pure-perl modules, you may even be able to get away with pre-installing them (i.e., just placing their files in your tree). Of course, since you're then distributing the result, you'll want to consult with the lawyers about proper attribution and licensing, but that should cost a fraction of what developing some of the modules from scratch would be anyway.
The only thing I can see where you can't just install or upgrade willy-nilly might be perl itself, or other external dependencies (such as Oracle if you want to use DBD::Oracle, or expat for XML::Parser). Most modules, however, should not have such a limitation. With a little thought, most other issues should be easily worked around, and even external dependencies can sometimes be worked around, too.