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
