I'm glad to see Ævar's The CPAN client version-less dependency problem, because it discusses a real problem. In the absence of specific information about dependencies, what should installers do?
Unfortunately, that's the wrong question.
Have you ever read code which performs user input validation deep in its guts, way down in code which has layers of insulation between user input? I have. I take no small pride in removing this validation code and putting it where it belongs: as close to the input as possible. This has at least two benefits. First, it allows for the possibility of reporting user errors in the view and dispatch logic, where it belongs. Second, it removes clutter from code which can document its expectations appropriately.
(I realize that high security applications may need extra paranoia and I submit that you should have effective testing of the interfaces between components to satisfy you that unrealistic data never enters the application, but it's still a general rule.)
If you're confident that you've dealt with all sources of errors before a certain point, don't worry about them after that point.
With that all said, perhaps the client side of the CPAN installation is the wrong place to handle these dependencies. After all, the developer of the code has presumably installed dependencies locally and has run tests against them. Why shouldn't Module::Build or ExtUtils::MakeMaker check the installed version when bundling the distribution and include that as a recommended minimum version in the META.yml file?
It's no worse than "Install whatever version you want" and it at least has the data point that someone had that version working. It also requires no changes to the installers with fragile or odd heuristics.