Hola de nuevo. Creo que la solución es más fácil de lo que parecía:
<style>
a:link {color:red}
a:visited {color:pink}
a:hover {color:green}
</style>
Es decir, poner a:visited antes de a:hover
A mi al menos me ha funcionado. Espero que a ti también.
Saludos,