If you are adding a contact in MOC that does not have msn.com/hotmail.com e-mail addresses, you need to write them in the format address(domain.com)@msn.com to add them correctly to the list. The reason seems to be that you are not federated to anything other than msn.com/hotmail.com.

If the person with a non-msn account adds you, everything works fine.