Its not really related to PREREQ_FATAL for a lot of reasons.
1. You can't depend on yourself here, so you can't demand that a CPAN client does *not* have an older version of yourself. ( Actually, that might be viable, I just haven't heard of it being done before and the support is likely very scant )
2. Unlike PREREQS, you're not providing *any* mechanism by which the CPAN client can resolve it on its own.
I see it more like "Your system can't support this because of a problem outside the scope of a CPAN Client", which is used extensively in everything that uses XS or external dependencies.
For instance, if your library requires a binary in $PATH that can't be provided by CPAN, then an "exit: N/A" from Makefile.PL is appropriate.
If for instance, your library requires a linkable .so in the library paths, or a .h file in @INC paths, an early "no, I cannot actually continue" is appropriate from Makefile.PL ( signalled by an early exit
So here, you very much have the same "this is a problem that will happen when you use a CPAN client and your CPAN client will do nothing to help you" problem space.
Similarly, your approach of "just warn and then continue" with the bin/lib example cases would map to the tool installing anyway regardless of the lack of a `bin/` , and then later failing in confusing ways when something tried to use your module and it didn't work.
And in the lib case, you'd be installing the pure-perl parts without any of the XS parts, and then again, the module would break when somebody attempted to use it, without it being obvious why, and you'd be a long way from the problem when that happened.
Similarly, "I'll install, but I won't actually be there and usable after I'm installed for ways that a CPAN client can't help with, and I refuse to help with in any way" is essentially a violation of the CPAN dependency contract.
If your module *cannot* be used, then it *should not* be able to be installed.