Here is my proposal for what to do:
1. Find all known mailing lists in the to/cc headers, and simultaneously crosspost to those newsgroups
2. Only rewrite a message ID if the news server has one on the server that does not represent this message.
This means that all of the problems with message IDs should be limited to people who put the mailing lists in BCCs, or people who are sending to mailing lists on multiple servers that inject into NNTP in different places.
I do not yet have a patch for either yet.