Just for the record, I found the flaw in this scheme. One of my included modules includes 'Storable', which tries to include 'Log::Agent'. If it fails then the 'Storable' module does something else. The above @INC scheme forces the user to install the conditional module. This shouldn't happen.
So back to the old method (slightly refined to handle module versions and import lists)
our @missing =
grep !eval "use $_; 1",
split /\s*\n\s*/, "
A::B wq(a b c)
" and die "Please install CPAN modules: cpan -i @missing\n";