Try this whether your contacts are in iCloud or in your chosen email account
(You might want to back up the phone first)
If your contacts are phone only and not hosted in any cloud then you have no remedy, STOP NOW
Close Contacts app then
If your Contacts in iCloud:
Settings, Your name, iCloud, Turn off contacts
If your Contacts in another email account:
Settings, Contacts, Accounts
Find the account with Contacts turned on. Turn contacts off
When asked if you want to keep a copy, NO! choose “delete from my iphone ”
Open Contacts app and it should be empty.
Power the phone off and back on.
Then
If your Contacts in iCloud:
Settings, Your name, iCloud, show all, Contacts. Turn it On
If your Contacts in another email account:
Settings, Contacts, Accounts
Find the account with the Contacts again. Turn contacts On
Open Contacts app and it should be re-populated.
Then try the contacts or messages again see f the names returned.