gmail no permite entrada de correos sin datos del emisor como una manera de evitar el spam, para poder enviar a gmail tienes que agregar algunos encabezados, intenta algo así:
$headers = "To: nombre <
[email protected]>\n" .
"From: From Address <
[email protected]>\n" .
"MIME-Version: 1.0\n" .
"Content-Type: text/html; charset=iso-8859-1";
y agrega el header al final del mail():
mail($mail,"Formulario de Consulta",$message,
$header)
te recomiendo que hagas pruebas a otro e-mail (que no sea gmail ni hotmail), una vez que te asegures que funcione envíalos a tu gmail