Since I have been using Outlook 2010, search is slow and it always starts finding older items first, which is really frustrating and it seems I am not the only person having this issue.
After investigating on this matter, I realized I had turned of Microsoft (Desktop) Search to look into my email (and contacts). This due to the fact that every time I did a search in the start menu, my outlook items were showing up. This however seems to crippled the search from Outlook itself.
The solution is to enable the Microsoft Search via Outlook options:
In the Indexing options, make sure your Outlook account is added to list of items to be indexed.
After all items are indexed, things should work better now and with an additional bonus that the search is much much faster. Coming back to the reason why disabled this in the first place: showing outlook items in the start menu. Well this can be disabled by setting a registry value:
Path: HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer\
Key: NoSearchCommInStartMenu (DWORD)
After setting this key to 1, your outlook items will no longer be shown in the start menu search results.