The bad header is usually due to strange character sets or a bad news client being used to post the article. Usually you'll see this in test and binary groups where people may be testing out there own posting programs. 20% seems high. I was getting that sort of number when I was using alt.test. But a real newsgroup only rejects a tiny percentage.

The script actually puts out the rejected header message when it can't find a message id in the header. This is usually due to the reasons above.