Hello, David.

I came across this bug report for notmuch when I wanted to report it myself:
https://www.mail-archive.com/notmuch@notmuchmail.org/msg46633.html

I didn't see an obvious way to respond on the mailing list (tho I now
subscribed for next time), so I hope a direct response is ok.

You've already reproduced it, but I wanted to give additional
information. I used a test case in my emails and threw it at git
bisect. The commit introducing this behaviour is
491b1f4b4082bee18418942846ec6508856be7b4, where you fixed the order
for a loop. Reverting this results in the correct order for threads
with an unknown Message-ID in In-Reply-To (which is the case in my
thread as well).

Not having an email with the Message-ID probably is quite a normal
situation, for instance when people reply to someone and add someone
else to CC. I guess the right behaviour would be to simply go by date.

I tried to build a test case myself and maybe a patch, but I'm rather
lost with the tests... and about 200 of them fail for me. No idea
whether they should pass or not.

Ciao
  Oliver