Logging a Call - Search is not working

When I want to log a call, I have the search feature.
However if I enter the name of a contact, this contact is not found.
The contact is only found if I enter the account name of the contact. But when I enter just the name of the contact, it is not found.
I create the contacts with firstname familyname
When I search for firstname some contacts are found sometimes.
When search for the familyname (which is quite common on the phone) nothing is found.
This often leads our supportReps to create a new contact, even if the original contact is already existing.
And since they don't aks for the firstname, a new contact is created with just the familyname.
And if time entries are added to the call I can not change the contact back to the already existing correct contact.

Kind regards,

Jürgen