a) requires that the module in question has a Meta.YAML file

That's why there's Module::Depends::Intrusive :-)

b) only checks what modules are required to make and load the module. This will miss, for example, modules that do on-the-fly requiring i.e. that depend on another module in certain situations but do not depend on that other module for just making and loading the original module.

True, but it's impossible to determine this programatically in the general case. The other issue is that it conflates build-time, test-time and run-time dependencies. If you're dealing with PPMs, for example, you don't really care about build- or test-time dependencies.