Precisamente ayer estuve lidiando con un problema similar.
Mi provedor de hosting deshabilito la funcion mail() y encontre
http://phpmailer.sourceforge.net/
Aqui es una clase donde tu puedes enviar correos con tu smtp que quieras incluso el de gmail o el de tu servidor y tiene muchas funciones como formato html, atachments, etc.
Checalo a mi me funciono muy bien.