I had the same problem with Huawei P10, but it seems I could solve it. Within "Contacts" there is an option called "organize contacts" and within that "Rebuild index data". I tapped on it and when rebuilding completed (within a couple of minutes) the feature of getting a list of contacts as a string, contained by their name, is being typed in worked again.
I have the same issue. Example: I have a dozen "Adam"s in my contacts, but the dialer won't find them. The only workaround I found is to type "Ádám" or something similar with strange vowels, then it finds them. (I have a Vodafone Smart Prime 7 with Marshmallow, and I have two languages set up in google keyboard, never had this with earlier android versions or different phone.)
i had the same problem in my Le Eco 2 phone and i just did very simple thing
1st export all your contact to phone storage then delete all your contacts and them import back all contacts from your phone storage.
This worked for me and i believe it will work in all android phones.
I myself had the same problem with my Huawei P10. Read some answers and found, in the Contacts section the 3 dots in the right lower corner of the screen. Pressed them and then again pressed Organise Contacts. There you will find the last option - Rebuild index data. By selecting that option I fixed my problem. Great for all my contacts to be back in the Dialer !