Modificando el query y agregando otro IF debajo del de la validación del usuario.
$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>";
}