It would be great to use the INTHREAD extension (which is always available when THREAD=REFS is there); this could avoid fetching threading info for the whole mailbox at the rather small expense of not having full sorting available all the time. However, the UID-based sorting suggested in #321372 should help here.
Thank you for the bug report. As this report hasn't seen any changes in 5 years or more, we ask if you can please confirm that the issue still persists. If this bug is no longer persisting or relevant please change the status to resolved.
Trojitá is no longer maintained, please switch to a maintained alternative like https://apps.kde.org/kmail2/ Sorry for the inconveniences.