Something that has helped me a lot recently is to package ALL the dependencies for an application together, with an automated build process. Take a look at the way Krang handles this. It includes the application code, the templates, the executable scripts, the CPAN modules sources, and even the apache server source in one bundle that gets built by one script. This goes a long way towards fixing dependency problems and "wrong version" issues with CPAN. It supports building on the target machine, or building a binary that can be installed on multiple target machines later. I'd like to see packaging like RPM and DEB as an option eventually too.

An additional advantage is that you can put multiple versions of the app on the same machine safely. You have to be aware of things like common ports of course, but it allows you to have two versions of the same module on the same machine with no conflicts.