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”

Outlook 2010
Windows XP