I think it's reasonable to depend on other modules - no matter how unusual - without bundling them with your code. It's not as if it's hard to grab modules and their dependencies using the CPAN module. And if the machine you want it on has no direct access to the outside world it's still not hard. I install modules on just such a machine quite often.

In fact, I would go so far as to say that, in almost all cases, including some random module in your tarball is a BAD thing. Try searching CPAN for Test::More. It appears in several packages. It's at different versions in those packages too. Someone who's bundled it with their code may very well have bundled a buggy version. Better in my opinion to put it in the list of prerequisites for your module so that the CPAN or CPANPLUS module can fetch it for you.