For Outlook 2003 and previous and on Windows XP;
No, the native search does not support that; it starts with the first item
that is stored in the pst-file (this does not have to be the oldest in terms
of received)
You can do this when you install an indexing tool such as Windows Desktop
Search; http://www.microsoft.com/windows/products/winfamily/desktopsearch/default.mspx
When using Outlook 2007 or Outlook 2010 on Windows Vista or Windows 7, the
data in Outlook is indexed by default and results are indeed (usually) from
newest to oldest. Results are popping up that much faster that you usually
do not even realize which it is presenting first ;-)