No pues como trabaja con un Windows Live ID general, dudo mucho que los puedas recuperar, aunque igual y si aún te tienen de contacto te sale como que te agregan a tí.
De todas formas igual espera más comentarios, pero lo que si recomendaría es que no hagas algo tan radical para no enviar SPAM, mejor agrupa a los que se los quieras enviar XD en un grupo, o si es por parte de un virus, pues mejor acaba con él jeje
Saludos!

No se si aplique en este caso, ni si vaya a ser de utilidad... pero lo que a mi se me viene a la mente es: desde Messenger presionar [de ser necesario] la tecla Alt - Herramientas - Opciones; seleccionar Privacidad [lado izquierdo] y ahi podra ver 2 listas, una de permitidos y una de bloqueados, en esta ultima dar click derecho sobre cada contacto al que quiera re-agregar y mover a su lista de admitidos [dar click en ambas opciones]