Pues no hagas el link directo, sino a traves de una pagina que cuente las visitas y luego redirija el navegador a la pagina en cuestion...
Código PHP:
//LIGA OK:
<a href="visitas.php?id=<?= $row["id"]; ?>url=<?= urlencode($row["url"]);?>">Click para ir al sitio</a>
//Pagina visitas.php:
<?
//Te conectas a la BD y todo eso...
$id=$_GET["id"];
$url=$_GET["url"];
mysql_query("update tutabla set visitas=visitas+1 where id=$id");
header ("Location: $url");
?>