Outlook 2010 returns search results from older emails first.

Good afternoon all,
 
I have a client where if I do a mailbox search, I see results from 2004 appear first, then a few seconds later, results from 2005, then 2006 etc. The most recent results are at the top based on sort order, but it can take 20 to 30 seconds before any results from 2013 appear.
 
Most of the time the client is interested in recent results only and ideally the search should always return the most recent results first, and the older results last.
 
The client is using Outlook 2010 client – (14.0.6131.5000) SP1 MSO (14.0.7106.5001)
 
Thanks in advance for any help you can provide.

Dave...