I doubt fixing this requires rewriting mailman. It only requires dummy messages to be reinserted where they've been deleted and the archives to be rebuilt after this, just as if the correct procedure had been followed from the start. This, by the way, is by some orders of magnitude easier and quicker than fixing all the thousands of broken links across all the wikis.
While we're on it, maybe someone will understand why the August archive is now full with "no subject" emails which seem to come from other eras and have the most random ids. http://lists.wikimedia.org/pipermail/wikitech-l/2012-August/thread.html#1052
Nemo