jaruso, el asunto es el siguiente:
si en el enlace tienes la imagen insertada en el html
Cita: <a href="pagina.html">Enlace<img src="imagen.jpg" /></a>
y al ser visitada quieres poner la nueva imagen como background en lugar de insertada:
Cita: a:visited{
background-image:url('imagen2.jpg');
}
¿qué es lo que hará desaparecer la imagen insertada del HTML? nada.
Tienes entonces varias alternativas: puede empezar por no incrustar la imagen sino ponerla como fondo del enlace, y cambiarla en :visited por otro fondo; puedes usar algo como
a:visited img {visibility: hidden;}
Habría que ver tu caso específico para ver qué es lo mejor.