I've had similar problems with OpenBSD. And Solaris is even worse, as it doesn't come with a C compiler.
I tend to favour the dual Perl approach, but I largely work in a server environment. As you have pointed out, that makes a huge difference: code (whether Perl or otherwise) is not so much run on a server as it is added. It's trivial to start a script with #!/usr/local/bin/perl on a server. It gets enormously harder when the script is to run on machines outside the sysadmin's (or the sysadmin's team's) control.
A solution I have commonly seen is to simply not use CPAN modules. I know that goes against all the "best practices" ever published; but several sysadmins I know have decided it's better to re-invent the wheel than to jeopardize a running system with 3rd-party code that typically comes without warranties. In fact, one friend of mine is a sysadmin in a finance company, and there are policies in place explicitly forbidding the use of CPAN modules.
I hate to say it, but there is a lot of merit in that approach. And if there are issues with distributing code across a number of machines because of CPAN dependency issues, re-inventing the wheel is a very reasonable option.
I've moved to a much more relaxed environment (and the lower pay that goes with it) in the last 8 months. It's been nice to use CPAN again without having to justify it to everyone and their dog.