A year to the day after Ian Tegebo sent me a patch for CPAN::FindDependencies, I've finally applied it, hacked on it a bit, and released it.
With Ian's magic, it can now resolve dependencies for distributions where there's no META.yml but there is a Makefile.PL. Since this involves downloading stuff form the intertubes and executing it, this feature is disabled by default.
Obviously, I won't enable this on deps.cpantesters.org.