Yes. It's RFC. I spoke about bug in thunderbird which change uid of 
mails. It takes some mails (not all -  forexample 900 from 2200).

First step, it delete msg.
Second step, it add deleted msg back and msg have new - higher uid.

Is't prohibited by any RFC?

forexample:

-rw------- 1 root root     1966 2012-05-29 10:34:35.000000000 +0200 17034.
-rw------- 1 root root     1755 2012-05-29 10:20:36.000000000 +0200 17033.
-rw------- 1 root root    72072 2012-05-29 09:48:14.000000000 +0200 17032.
-rw------- 1 root root     3190 2012-05-28 23:08:04.000000000 +0200 17031.
-rw------- 1 root root  7058824 2012-05-28 18:56:39.000000000 +0200 17030.
-rw------- 1 root root   909212 2012-05-28 18:20:08.000000000 +0200 17029.
-rw------- 1 root root    60816 2012-05-28 18:03:39.000000000 +0200 17028.
-rw------- 1 root root    51626 2012-05-28 15:56:00.000000000 +0200 17026.
-rw------- 1 root root    52181 2012-05-28 15:04:31.000000000 +0200 16186.
-rw------- 1 root root    59747 2012-05-28 14:41:16.000000000 +0200 16187.
-rw------- 1 root root     2230 2012-05-28 10:19:54.000000000 +0200 16189.
-rw------- 1 root root    80081 2012-05-28 10:17:30.000000000 +0200 16182.
-rw------- 1 root root     4904 2012-05-28 09:58:57.000000000 +0200 16188.
-rw------- 1 root root    54790 2012-05-28 09:32:07.000000000 +0200 16190.
-rw------- 1 root root     3407 2012-05-28 09:09:37.000000000 +0200 16193.
-rw------- 1 root root     2341 2012-05-28 08:59:45.000000000 +0200 16192.
-rw------- 1 root root    42263 2012-05-28 08:52:39.000000000 +0200 16191.
-rw------- 1 root root     5841 2012-05-28 08:22:53.000000000 +0200 16198.
-rw------- 1 root root     3423 2012-05-28 08:13:12.000000000 +0200 16197.
-rw------- 1 root root    16184 2012-05-28 08:00:07.000000000 +0200 16196.
-rw------- 1 root root     7166 2012-05-26 23:19:37.000000000 +0200 16195.
-rw------- 1 root root    11320 2012-05-25 17:01:20.000000000 +0200 16194.
(i set time under time of mails .. in the fact hundreds mails have 
same time but then is hard ilustrate problem)

If you sorting these mails under uid then you get only mess.

Thunderdird and Outlook doesnt have this kind of problem cuz they are 
sorting under time and not under uid. It's not bug in horde algo. 
Horde isnt immune to this kind of problem and change sorting under 
time and not under uid will make horde better - it will make horde 
immunne to thunderbird crap :).  Sorting under time have no hole. 
Under uid obviously have :(.

Of course you can.

*Please* read RFC 3501. The definition of UIDs (Section 2.3.1.1):

...Unique identifiers are assigned in a strictly ascending fashion in 
the mailbox; as each message is added to the mailbox it is assigned a 
higher UID than the message(s) which were added previously...

Michael .. sorry .. but you are wrong.

From for me unknow reason latest thunderbird can occasionaly run 
after start and login  weird proces. During this process:
a) delete message
b) create same message again

I know it cuz i have special hook in cyrus and i log every change as 
read, delete, purge, and etc/

I think that you can't rely on UID anymore :(

[..snip..]
  Yes, I know this difference. And that is the problem. We did sorting 
by message date and it's not visible in any logs. Maybe old Cyrus 
(2.2) implementation?

The sorting is exactly right.

Your messages:

UID 840 = Mon, 01 Feb 2010 18:41:58 +0100
UID 842 = Sat, 19 Dec 2009 21:47:03 +0100
UID 845 = Sat, 19 Dec 2009 21:47:03 +0100
UID 1165 = Wed, 18 Aug 2010 08:55:56 +0200

Sure enough, the sorting is correct:

C: 3 UID SORT (ARRIVAL) US-ASCII UNDELETED
S: * SORT 840 842 845 1165

And can be verified since UIDs are always increasing in a mailbox 
based on arrival date.

There is no attempt to sort by *message* date in this log.  Arrival 
date != message date.

  And here is screenshot.

  Here is it

It would also be more useful if you could clear your cache and provide 
the full IMAP logs of a single login.  E.g. login, sort a mailbox by 
arrival date, and then switch sorting to message date.

This looks even more like a search for arrival date (NOT message date):

C: 3 UID SORT (ARRIVAL) US-ASCII UNDELETED
S: * SORT 274 401 839 840 842 845 1165 9461 9477 9994 10015 11295 
11643 11735 11736 19664 21797 22720 23659 24476 26511 26548 26551 26552

No, this looks like sort by arrival date:

C: 3 UID SEARCH UNDELETED
S: * SEARCH 274 401 839 840 842 845 1165 9461 9477 9994 10015 11295 
11643 11735 11736 19664 21797 22720 23659 24476 26511 26548 26551 26552

Check your prefs.

And here is log for sorting by message date (wrong too).

Sorry for delay (vacation and other work taks)...
Here is a log when sorting by delivery date (bad in both traditional 
and dynamic)

You will need to provide IMAP logs during the page loads when you are 
switching to date sort and then switching between date sorts.



To further debug this issue, we need details of the IMP -> IMAP/POP 
communication.

To enable debugging, see instructions contained in 
imp/config/backends.php (the 'debug' config parameter).

Debugging should not be enabled on a production server,   Attach/post 
only the portion of the log that directly deals with the problem 
reported (it may be simplest to clear the log file and then perform 
the event that causes the error).

Hmm, sorry unable to attach, here is link:
http://users.fs.cvut.cz/jiri.solc/horde/20120208_1047_28.swf

Sorry SWF did not atach, trying again as zip :-)

Here is a screencast whats happening. When I sort by message or 
arrival time I have same results (page is reloading correctly). 
Currently don't know why - can dive into source, but not now (too much 
tasks in work). Tell me what do you need, I'll try to help.

Since this is the default date sort, this is almost certainly what is 
happening.  I cannot reproduce.  Closing unless this can be reliably 
reproduced as incorrect.

You are most likely sorting by arrival, not date.

IMP is doing bad sort by date in any folder. We are using Cyrus 
2.2.13, folder is correct (to be absolutly sure we do reconstruct too) 
and when talking to cyrus via telnet and doing sort - everything is 
okay. But see attachment, sort by date is not valid (not only in this 
screenshot).