Shoutbox

When you click on the 'Messenger' category, you should see a list of all the contacts who where invited to use Messenger.
I haven't found a way yet to re-add contacts in bulk from the 'Contacts' section on the Windows Live pages though.

But you can do it one by one by clicking on the contact's name/email.
This will take you to that contact's information page where you can edit its profile etc.

If the contact isn't added as a Messenger contact yet, you'll see "You're not friends with x in Messenger. Add as friend" in the top header:



So, go to the 'All Contacts' category and click on a contact's name/email.
Then click that link, showed above, to send an invitation.
This should send an invitation and should mark the contact as a Messenger contact.
(the contact needs to accept the invitation before you can chat of course)

Note that when you change stuff on the 'Contacts' section, it can take some time before the changes take effect.
So give it some time before clicking on other categories only to find your contacts aren't listed there yet.