If the PAB entry has the first and last names in the First name field, when they're converted the name is not parsed into the appropriate First name and Last name fields. Since the Last name field is empty, you can no longer use it to resolve the addresses. This gives the impression that the Contacts folder is not being used to check email addresses.
If you have a large number of contacts it may be easier to recreate them if you know exactly which records do not have a populated Last name field. You can isolate those contacts with no last name and are not Distribution lists, by creating a custom view.
If you type a partial name for an individual Contact, into the To field of a new message, it will resolve properly. This is also true of partial names for DLs stored in the PAB. However, this is not true of partial names for DLs stored in the Contacts folder. The names of DLs in the Contacts folder are stored as one complete property rather than three (first name, middle name, last name), as are individual contacts. This assists in maintaining their sort sequence when switching between last-name/first-name and first-name/last-name displays but does not allow partial entries to be expanded into full names.