Index: mail/ChangeLog
===================================================================
--- mail/ChangeLog	(revision 37524)
+++ mail/ChangeLog	(working copy)
@@ -1,3 +1,10 @@
+2009-04-22  Milan Crha  <mcrha@redhat.com>
+
+	** Fix for bug #563954
+
+	* message-list.c: (regen_list_exec): Sort UIDs before
+	using them to obtain proper order when without sorting.
+
 2009-04-13  Chenthill Palanisamy  <pchenthill@novell.com>
 
 	Fixes #467659 (bnc)
Index: mail/message-list.c
===================================================================
--- mail/message-list.c	(revision 37524)
+++ mail/message-list.c	(working copy)
@@ -4169,6 +4169,8 @@ regen_list_exec (struct _regen_list_msg 
 
 	//camel_folder_summary_reload_from_db (m->folder->summary, NULL);
 	if (!camel_operation_cancel_check(m->base.cancel)) {
+		camel_folder_sort_uids (m->folder, showuids);
+
 		/* update/build a new tree */
 		if (m->dotree) {
 			if (m->tree)
