PHPMailer es una clase php para enviar e-mails, especialmente, a través de un servidor smtp. Es muy sencillo de utilizar y es cómodo incluso para enviar archivos adjuntos. Entra en su web, ahí verás muchos ejemplos, algunos sencillos y otros más complicados.
Entre tanto, voy a probar ese código a ver si a mi me funciona o si me doy cuenta de lo que falla.
edito: El código funciona correctamente. Acabo de enviar un correo a una cuenta de hotmail y ha llegado... Además he usado una cuenta en 000webhost.com. Dicho esto... No tengo ni idea de qué puede estar ocurriendo :S