I agree with brian_d_foy, list a minimum version in the dependency only if you know that earlier versions break the module. The same thing goes with versions of perl BTW, there is no need to start with use 5.8.7 if the module might work in 5.6.2... or 5.004!.

This way you will start with #1 and eventually end up with #4.

Of course this will work best with good test coverage (Devel::Cover is your friend), and it can be a real a pain to make sure your tests work with old versions of perl, but I think this is the right thing to do.