When you go into the Contact card for one of the contacts this is happening to, what is selected for the Display As field? If it just has the persons full name, highlight the name and delete then press TAB and Outlook should auto fill the field with name and then their email address in brackets. This will then show both when the Check Names feature is used.