El problema no es tuyo, y por tanto no lo puedes solucionar. Si miras por internet muchos sitios te dicen que metas correos que no sean de hotmail pq son una mierda.
De todas formas, yo tambien tengo una web con funcion mail() de por medio y me funciona bien, a lo mejor si puedes hacerle algo al smtp... (pero de todas formas la culpa es de hotmail...)