Version:           1.8 (using KDE KDE 3.4.0)
Installed from:    SuSE RPMs
OS:                Linux

As part of a SuSE upgrade from v9.1 to v9.3, the bundled version of KDE went from v3.2.1 to v3.4 and kmail went from v1.6.2 to v1.8.

In the new version of kmail (v1.8), sorting the messages in a folder by "Date", either ascending or descending produces the same (expected) results as in the previous version.

However sorting messages by "Date (Order of Arrival)" produces drastically different results in under kmail v1.8 than under v1.6.2.  Furthermore, the messages are not sorted by the order in which the arrived into the folder (or to kmail).  

To test this I have pulled messages from the same POP mail account to two different machines - one running Suse v9.1/KDE v3.2.1/Kmail v1.6.2 and the other running SuSE v9.3/KDE v3.4/Kmail v1.8.  In both cases, messages are sorted by "Date (Order of Arrival) ascending".  Under the kmail 1.6.2 instance the messages are in the order in which they were pulled down into kmail.  Under the v1.8 instance the are not; they appear to be ordered based upon the message header, but I have yet to confirm this.

This appears to be similar to an issue which existed in early editions (around v1.1) of Kmail - it may be the resurfacing of that bug.