Bueno, a reserva de pensar en la posibilidad de hacer el filtrado con SQL, yo podría sugerir.
Código PHP:
for ($i = A; $i!="AA"; $i++)
{
$qask = mysql_query("SELECT COUNT(*) FROM empresas WHERE empnombre LIKE '$i%'");
$filas = mysql_num_rows($qask);
if($filas > 0)
echo '<a href="'.$pag.'?letra='.$i.'">'.$i.'</a> ';
}