Are these messages sent to a group? If they are assigned to a new group each time, then one of the email providers (either yours or the other side) strips the Chat-Group-ID from emails and Message-ID. This is a typical behavior of outlook/hotmail: Problem in using hotmail.com/outlook.com
What causes a change of setup on the sender’s side?
This means that Autocrypt header has changed. Probably you have received a message with Autocrypt header, and then without Autocrypt header (because it was removed by the email provider).
I looked into the header and found not many of the Id’s, mentioned in Your list of criterions:
If Message-Id is not of the form Gr.something.somethingelse@example.com or same but with Mr. prefix, then some provider is rewriting Message-IDs. If there is no Chat-Group-ID in the message sent to the group, then provider also removes this header. Also there must always be an Autocrypt header in messages sent by Delta Chat.