Very bizarre issue - Exchange 2010, user on windows 7 with office 2007 non-cached mode.
Instant search works for emails, events but when using it for contacts, it is not bringing up all applicable results.
All attempts to remedy have failed, user said he's not sure when it stopped working but it's been several months. These have been the few things I could try and all failed:
1 - rebuild outlook profile
2 - test on new PC, and citrix - able to duplicate
3 - repair install for office
4 - manually reindex
5 - delete and re-enter one of the contact records that is not search-able
6 - exchange database healthy
Specifically, user has 2800 contacts. 3 have the last name Richter. Search on "richt" brings up only the first record. Searching on the first name i.e. "Dan" still does not bring up nor does a company name search.