When I showed Benjamin (a college of mine) my TPF 2010Q3 grant proposal, we slipped to a discussion about deploying Perl software. Nice (and recent) list of different approaches can be found @modernperlbooks.com. To sum it up => TIMTOWTDI. Which is good, but none of those is perfect. The Perl+CPAN world is way too complex.
During out discussion with Benjamin I proposed an idea of shipping the application altogether with the OS. Insane? The base Debian system is ~190MB, all the rest is needed for the application. Then deployment will be a matter of running this system on a virtual machine, somewhere in the cloud or in a simple chroot. (btw any Linux distribution can have any other Linux distribution working in a chroot) The files will never clash, all the "machines" would be dedicated. No fear of putting files where they belong to.