Can you guys select one of the affected messages and then select
View -> Message -> Long Headers in Mail.app?
Next, have a look at the "message-id" header. Does it contain the '%' character?
(
Forum link for my own future reference, in case this turns out to be the same problem.)