Find/Advanced Find returned results order and Finder folder PR_CREATION_TIME property value correlation

[Ross]

I am running MS Exchange 2003 SP2 and my users run MS Outlook 2003. We
do not have Full-Text Index implemented. All searches performed by
users are done against mailbox databases. Implementing Full-Text Index
is out of the question. No users are configured with Exchange Cached
Mode. There are few users (VIPs) that have higher mailbox size limits
(up to 4GB) than standard mailboxes. All of these users' mailboxes are
in the same mailbox database. They also happen to keep most messages
in one folder - Inbox. The number of messages largely goes beyond MS
recommended maximum number of 5,000 items per folder. Few of them have
anything between 10,000 and 50,000 messages in Inbox. Searching Inbox
takes anything between 5 and 15 minutes to complete.
These "special" users are complaining that since two weeks ago, when
they perform Standard Find or Advanced Find, the returned search
results start to appear as follows: first, messages received before
the date two weeks ago (let's call it "demarcation" date) and only at
the end of the search process newest messages start to appear. I have
confirmed this to be the case by performing searches in those users'
mailboxes from my workstation. I also did perform searches against my
mailbox which is on a different server and, have noticed the same
order of returned results. The "demarcation" date is different and the
results are returned much faster (I don't have that many messages in
any of my mailbox folders) therefore it is a non-issue to me. However,
the same behaviour is observed. Repeating shortly after (ie. few
minutes or few days later) the same search returns the results in the
same order.
I have searched for any information that would provide an answer, but
did not find anything. An answer from this KB - http://support.microsoft.com/kb/308608/en-us
- does not seem to apply. These mailboxes/users have not been moved
for few years.
I have also noticed that the property PR_CREATION_TIME of Finder
folder revealed in MFCMapi has the same value as the "demarcation"
date. This is also true for my mailbox. Deleting all subfolders in
MFCMapi, gets rid off all numbered search folders (these, I presume,
are ad hoc folders created through Find and Advanced Find) and clears
the results from named Search Folders (Large Emails, For Followup
etc.). The same result is obtained via Outlook switch /cleanfinders.
However, the above mentioned property of the Finder folder does not
change nor does performing new search or repopulating existing Search
Folders.
My question is - what can be done, if ever possible, to have the
returned search results appear from newest to the oldest. Is there any
correlation, other than apparent one as described above, between how
the results appear and the value of PR_CREATION_TIME property of
Finder folder. If there is a direct link, what process or event is
responsible for changing this value. This property had certainly a
different value (a different date) two weeks ago and, I presume, it
will change again at some point.
Thank you for any information helping me understand the issue.

Ross