We had a similar issue where I worked beforehand.
We put the unnamed (incomplete) contacts at the top of the list, so the user could quickly see that they didn't complete the contact info. For us (an enterprise level co.), our records could be quite lengthy.
We considered those incomplete tasks, so we wanted to bring this to their attention.
If it's important they complete the record, you can have a graphical indication to call it out to the user, so they don't think that the system is at fault.
If it's crucial, you could let the user know when they're creating and saving incomplete records at the time they're entering them. That way the system is responsive. You could give them the option to edit it right that moment, or if the system is forgiving, let them come back later and finish.