When I got my Droid 6 days ago I ran into the same problem. I took my old phone and my new phone to verizon the next day to have my contacts transferred and the voice search feature would never call any of my contacts but the voice dialer would. After some extensive searching I came across the answer. This assumes that your contacts are checked as searchable in the system search settings.
For the voice search feature, contacts are only searchable if they are Google contacts and more specifically, "My Contacts". The transfer that verizon did for me created "Phone-only Contacts". Google contacts are synced with your google account. Exchange contacts don't seem to work either. So I went online to verizon's backup assistant website and exported my contacts to a csv file. Then I went into my google account and imported those contacts. When doing so, make sure your contacts are "My Contacts" not just "All Contacts". It only works if they are under "My contacts" (or friends, family, etc which are subsets of my contacts).
I feel like this is a bug as it should search all contacts like the voice dialer but in the mean time this works for me.
Hope this helps.