ya lo probaste en algún hosting como 000webhost por ejemplo? si te funciona ahí es porque la configuración de tu servidor de correo no esta del todo bien.
podrías usar la clase phpmailer también que trabaja muy bien. lee aquí un poco sobre los dos métodos.
http://mundo-php.blogspot.com/search/label/correo