It may be that they previously deleted you or you have them only as hotmail contacts and not as msn contacts, first at all take a look on hotmail's contact list and check them all to verify they are msn contacts, if so...
I think you can take a look here:
"Contact list rebuilder"
I'm not quiet sure if will work for you, once it worked for me, you need to know it will login your account so, i highly recommend you login in mns any other account that you have added to your main account before run this website, that way you can see if anything weird happens, and after you run it change inmediatly your password on hotmail's website
Wish you good luck!