Muy buena respuesta por parte de blog.faqoff.org

Copio y pego del artículo original porque yo perdí una.

Los pasos a seguir para recuperar la cuenta son:

1. Entrar en la página de soporte de Live y seleccionar el servicio que te interesa (en nuestro caso Windows Live Hotmail)
2. Rellenar el formulario con tu nombre, la dirección de correo donde quieres que te respondan, la dirección de hotmail o ID que has olvidado o te han robado.
3. En tipo de problema elegir pérdida de datos y en el recuadro adicional aportar todos los datos que recuerdes como cuándo fue la última vez que tuviste acceso, cuántos mensajes tenías en la bandeja de entrada, etc…
4. Espera a que te respondan. En la respuesta lo normal es que te hagan preguntas sobre los datos que aportaste al crear la cuenta tales como ocupación, fecha de nacimiento, provincia, etc… Si los datos son correctos (de ahí la importancia de haber dicho la verdad) lo más probable es que te restablezcan la contraseña.
5. En el caso de que en luga de pérdida, tengas constancia de que te han robado la cuenta, denuncia los hechos a la policía. Microsoft no te proporcionará directamente la información para que encuentres al culpable, pero si la policía la solicita mediante orden judicial colaborarán con el proceso.

Enlaces que te interesan:

blog.faqoff.org
Artículo original no te lo pierdas.

support.live.com
support.live.com