Tuve el mismo problema ayer y encontré una solución. En los viejos tiempos solía poner los enlaces con subrayado y enlaces visitados sin, para ser más simple para que el visitante no haga clic en el mismo enlace dos veces.
Ayer tuve una sorpresa al intentar hacer lo mismo y no estaba funcionando. Perdí 30 minutos hasta que encontré en Internet que desde 2007 todos los navegadores limitaban las propiedades que puede poner en "visitado" por razones de seguridad. Son solo como 6-7 propiedades que puede configurar como "visitado". Y uno de ellos es el color del borde. Entonces pensé en establecer el subrayado en none, y usar "border-bottom-color" para subrayar. No puede establecer "border-bottom-color: transparent;" para visitado, pero puede establecer el color de borde del mismo color que el elemento principal color de fondo. Eso hará que el subrayado sea invisible una vez que se visita el enlace.
<style type="text/css">
body{color:black;background-color:white;}
a:link{color:blue;text-decoration:none;border-bottom: 1px solid;border-bottom-color:blue;}
a:visited{color:red;border-bottom-color:white;}
</style>
O puede hacer a la inversa (lo que está pidiendo) estableciendo el enlace border-color de la misma como fondo y un color diferente para el visitado.
demo a la inversa: https://jsfiddle.net/stfr9f9a
gran pregunta, parece que un ': hover' hace aspectos' text-decoration: underline', pero 'a: visited' no lo hace por alguna razón, si un': link' tiene 'text-decoration: none' ... –