Entra en tu Messenger, y te vas al menú de Herramientas - Opciones. Una vez allí, puedes ir al menú Privacidad donde aparecen dos listas con la gente que has añadido alguna vez al messenger y a la izquierda los que están admitidos, a la derecha los no admitidos. Si vas una por una en cada una de las personas, pulsando con el botón derecho del ratón propiedades te puede parecer activada o desactivada la casilla de Eliminar.
Si la casilla aparece activada es que esa persona te ha borrado de su lista de personas, o simplemente que esa cuenta ya no existe.