no hiciste lo que te dije la ultima vez, agrega otra consulta y validala:
$sql = mysql_query("SELECT usuario_mail FROM usuarios WHERE usuario_mail='".$usuario_mail."'");
if(mysql_num_rows($sql) > 0) {
echo "El mail elegido ya ha sido registrado anteriormente. <a href='javascript
:history.back();'>Reintentar</a>";
}