Oh but the torment continues. While CPANPLUS does have an uninstall, it is just a wrapper around ExtUtils::Installed functionality, which only reports on installed modules inside the system perl tree. The more I learn the more it seems there is no current mechanism for doing what I want to do. So must either write it myself (a daunting task) or abandon the idea.
I've been in deadlock over this MakeMaker deinstall deprecation problem for the last month. I looked into slurping perllocal.pod before and after the install & storing the change somewhere. I also looked into overriding the MOD_INSTALL variable in the generated makefile with an install/deinstall program of my own. I looked at Module::Build. None of these seemed even remotely feasible. And so I started to think bitterly about backing down on my "reversibility is crucial" stance.
But now I've run across CPANPLUS thanks to the guys on Efnet's #perlhelp channel, and it apparently has an uninstall & does pretty much everything CPAN did. And by perl 5.10 it will replace CPAN. This may be the answer I've been waiting for, I'm checking it out right now.