Messenger deleted half my contacts and I can't re-add them

Hi,

I turned on Messenger one day only to discover half of my contacts were no
longer on my contact list, but relegated to "non-instant messenger
contacts." Of the contacts who Messenger deleted, they can still see me as
their contacts and message me as per usual but I cannot re-add them as
friends. Basically, I can only chat with them if they start a chat with me
1st.

I tried to re-add these friends by dragging their names back to my normal
list of contacts and that didn't work. I tried deleting the contacts and
re-adding them and that didn't work either. Also, I have tried uninstalling
Messenger and reinstalling, and replacing that driver that- when replaced-
seemed to fix other people's problems. However, none of these alternatives
have worked thus far.

Please help me!! :-)