se me hace raro que tengan la funcion mail() desactivada. en todo caso, si tu hosting es gratuíto, ponte en contacto y pregunta. por otro lado, si tienes un hosting de pago, volvemos al principio y algo falla.
imagino que no has obtenido el mensaje de error en la comprobación con el
if. incluso añadiendo el header que faltaba...
pues es raro.
outlook no te sirve porque para eso tiene que ser el propio usuario quien tenga una cuenta de correo configurada, cosa que con tanto hotmail, cada día hay menos.
yo, entre todas las opciones, elegiría encontrar el error. pero si te corre muchísima prisa, echa un ojo a
www.jotform.com. hay más webs como esa, es sólo un ejemplo. creas el formulario online y le dices a donde hay que enviarlo. ellos te dan el código y tú lo pones en tu página. incluso te ahorras el php.
saludos