a technique I have seen referred to as "monkey-punching"

Uh, I think you mean monkey-patching... though that doesn't seem to be what you're doing here, by your explanation you seem to be subclassing your modules?

My problem: SimpleServer is at version 1.21. When I try to publish the newer FOLIO module on CPAN, which is at version 1.0 ... How can I specify in the FOLIO module that I am not trying to define these classes, only add new methods? And so tell CPAN that I am not trying to provide alternative definitions.

CPAN does not care about the contents of the classes and whether you're trying to add or remove methods, or even if the code stays exactly the same. You must increment the version number for CPAN to recognize that the module is a newer version.

The problem appears to be you've duplicated package names across your distros, for example, you've got Net::Z3950::RPN::And in both Net-Z3950-SimpleServer and Net-Z3950-FOLIO. This is not a good idea because it will almost certainly conflict somewhere. Instead, subclasses need to have different names.

On the other hand, since the aforementioned conflicting classes all happen within SimpleServer.pm and FOLIO.pm, it appears these classes could be internal and not user-facing? In that case, there is another solution you could try: hide these packages from the PAUSE indexer. This does not prevent potential conflicts in the code, but it might appease the PAUSE indexer.