Pues no, eso no es así, así que tu Firefox debe recordar que has visitado ese enlace en algún momento.
Para estar seguros probemos este código:
Cita: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="es" lang="es-es">
<head>
<title></title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<style type="text/css">
li {display: inline;list-style-type: none;}
a:link {color:#FF0000} /* link en rojo */
a:visited {color:#00FF00} /* visited en verde */
a:hover {color:#FF00FF} /* mouse over en lila */
a:active {color:#0000FF} /* selected en azul */
</style>
</head>
<body>
<ul>
<li><a title="Ir al inicio" href="#1">Inicio</a> |</li>
<li><a title="contacto" href="#2">Contacto</a> |</li>
<li><a title="Aviso legal" href="#3">Aviso legal</a></li>
</ul>
</body>
</html>
Puedes probarlo
aquí para ver qué ocurre con los enlaces que ya has visitado y los que no.