Go into the Contacts area, right mouse click on the Contacts list which is not being used to resolve names and select Properties. Click the Outlook Address Book tab and tick the box for Show this folder as an e-mail Address Book. Click OK and try again.

If this is not selected the Check Names feature will not look in it to resolve a name.

P.S. It sounds as though the new contacts with the .msg extension have been copied into a new Contact list which is not the default one in the PST file, therefore the above setting is not enabled by default.