Just adding this little note:

I had the problem with multiple accounts that "new" mails are "way behind" the actual date so that sorting in "Date" order is suboptimal.
Sort by IMAP UUID (sorting by receiving time) should be the standard to go and not sorting by date.

Also it would be nice if "Mark all messages as read" would be implented, should not be a big issue :-)

Another way to solve this problem would be to rename "Date" column in "Sent date" (like Apple Mail does, for example) and to add a new column called "Received date".

The value for the latter can be inferred from the last "Received:" header and is much more trustable than the former, since it is written by the destination server.

Do not forget that often users need to see the actual date / time in which they received a certain message.

For instance, given these headers:

Received: by mail.myserver.com (Postfix, from userid 503)
id A24003C28017; Thu, 21 Jul 2011 12:40:02 +0200 (CEST)
Received: from mail.anotherisp.com (mail.anotherisp.com [11.22.33.44])
by mail.myserver.com (Postfix) with ESMTPS id C3D073C28017
for <user@mydomain.com>; Thu, 21 Jul 2011 12:39:53 +0200 (CEST)

...the Received date would be "21 Jul 2011 12:40".

It is just easier:

If you look at the Javascript code in Mail/view:

var inboxData = {"threaded": 0, "uids": [124474, 124473, 124472, 124471, 124470, 124469, 124468, 124467, 124466, 124465, 124464, 124463, 124462, 124461, 124460, 124459, 124458, 124456, 124457, 124454, 124455, 124453, 124452, 124451, 124450, 124449, 124448, 124447, 124446, 124445, 124444, 124443, 124442, 124441, 124440, 124439, 124438, 124437, 124436, 124435, 124434, 124433, 124432, 124431, 124430, 124429, 124428, 124427, 124426, 124425, 124424, 124422, 124423, 124421, 124420, 124418, 124419, 124417, 124416, 124415, 124414, 124413, 124412, 124411, 124410, 124409, 124408, 124407, 124406, 124405, 124404, 124403, 124402, 124401, 124400, 124399, 124398, 124397, 124396, 124395, 124394, 124393, 124392, 124391, 124389, 124390, 124388, 124387, 124386, 124384, 124385, 124383, 124382, 124381, 124380, 124379, 124377, 124378, 124376, 124375, 124374, 124373, 

... ... ..

You see the list of IMAP-Message-Numbers in the sort order defined by the user (defaults to date).
The simpliest thing would be to have an option that these list is really in descending order, so no extra sort by date has to be done.

The same applies when calling ..../Mail/folderNAME/uids.