I think the answer is somewhere between 3 and 4, and beyond this point the decision is based solely on how polished one wants one's CPAN module to be. We have to make a similar decision (i.e. how much work do we want to put into something) with just about everything we do. If you go with 3, maybe you can alert users that some earlier versions of the dependencies may work, and leave it up to them to do the final polishing of the piece.