So, one of my most annoying problems with mailman is the operation of its mail-news gateway. Due to the rewriting of message-IDs, most ways of sending messages causes threading to horribly break.
My proposal is this: optimize for the common case and avoid rewriting message IDs if not necessary. In other words, if the given message ID does not already exist on the server, do not rewrite the message ID. To handle most common cases of cross-posting to multiple mailing lists, find all mailing lists in the to/cc headers and use those to find all of the newsgroups.
Additionally, if it turns out that the message ID needs to be rewritten, the old message ID would be additionally saved to the references header. While it won't fix the threading totally, it should preserve some sense of the structure.
The biggest potential pitfall I see is if multiple mail servers inject the message into Usenet via different NNTP servers, so that some of Usenet sees it one group and some see it in some other group.
What are your thoughts on this?