Mira yo tengo mi sitio en un host que lo consegui de 100webspace (anda muy bien) Este servidor me bloquea el mail() de PHP. Mi truquito es usar PHPMailer una clase de php muy bien hecha y muchO mas funcional que mail() es muy facil de entender, yo la uso en mi formulario de contacto.
Ah mi web
www.maurishio.com.ar 
Suerte.-