The problem that took forever to isolate? Trailing whitespace on the Message-Id header line after the > was causing the message to get rejected.
This seems absurd to me. What ever happened to Be liberal in what you accept -- and conservative in what you send?
We've put a fix in the perl.org newsserver, and there is a fix in the latest Mail::Mailer that will stop it from adding whitespace. A fix for INN is being looked into. But I've been told to not hold my breath.