I figured this out. Note that this fix works for an iPhone 5s running iOS 12, with contacts synced to Google/Gmail. Your mileage may vary.
The problem seems to be that the phone numbers in the contacts app have lost the proper format. They should be in the form (123) 456-7890 and they have become formatted as 1234567890. It seems that iOS does a really literal comparison and it can't resolve this difference. I tested this theory by editing a contact to put a "+1" international code in front of the number. That forced the number into the correct format and the phone app and messages then displayed that person's name.
The challenge was how to do this without editing every phone number.
I fixed this by changing my region from the US to Canada. That evidently forces a re-formatting of the erroneous numbers. Then I changed it back to the US.
Go to Settings, General, Language&Region, Region, select "Canada", then press "Done" (I bet selecting any region would work). The change takes a bit of time. When it is complete, look at your recent calls, voicemails and messages--they should be displaying names. Look at your contacts--phone numbers should be correctly formatted. If so, the problem should be fixed. In any case, change the region back to "United States."
Good luck, I hope this works for you.