Thanks for the mbox file. It looks like the sorting never really worked. It must have been luck 
that all the mbox files I imported in the past had the correct order. 
Anyway, I fixed it in https://github.com/discourse/discourse/commit/ac743dab104d76d508a5a930c8d45f085c144ab2
Please bear in mind that it’s still possible for some messages to be appear to be in the wrong order. That’s because the post date reflects the value of the email’s Date header. It’s possible that the email client used the wrong date when sending an email. The import script determines the primary sort order by looking at the In-Reply-To and References header in order to prevent replies from showing up before any email it referenced.