I'm not sure if you're still interested in an answer
here, but I looked under the "Help" tab in the MSN
Messenger window (the one with the Contacts list),
selected "All Topics", then "Troubleshooting"--here's
what it says:
"If you see E-mail Address Not Verified after a contact's
e-mail address in your MSN Messenger contacts list, that
person has signed up for a Microsoft .NET Passport but
has not verified that the e-mail address belongs to him
or her.
A person's identity is verified when he or she responds
to the e-mail message sent by Microsoft for that purpose.
After the e-mail address is verified, your contact's
display name will appear in your MSN Messenger contacts
list instead of his or her e-mail address."
Look for an email from Microsoft in your friends' Inboxes
(that should have arrived shortly after you set them up)
and follow the instructions there. If you can't find
one, I think if you click on "Actions" (or one of the
tabs in that same Contacts list window), there should be
a listing that says "Verify e-mail address", or something
very similar. Click on that and follow the instructions
and your friends should be all set. It should show their
name on the list once you do, and allow them to change
their name if they want to in the future. You could
probably even do it through remote assistance and save
yourself a trip if you wanted to.
Hope that helps.