MS Outlook 2010 contact search unreliable

Microsoft Outlook 2010 with instant search disabled (Windows Desktop Search not installed).
Contact searches unreliable, sometimes returning sometimes not returning results for the same search queries.

Fixed by:

File > Options > Search
Uncheck “Improve search speed by limiting the number of results shown”