Prima di tutto devi scrivere la pagina in un linguaggio. Puoi scegliere una versione qualsiasi di (X)HTML, ma devi rimanere coerente.

Quello da te usato non esiste in nessuna gramamtica. A quel punto qualsiasi tipo di visualizzazione (anche non mostrare nulla) e` compatibile con il tuo scritto.

Se usi un editor, buttalo immediatamente; se usi un CMS o un linguaggio lato server, cambialo.

Poi hai ragione, i CSS servono anche per modificare la visuaizzazione dei link in caso di visitato, ma devi fare modifiche anche al codice HTML: quello che puo` cambiare e` lo sfondo, non l'immagine del tag <img>.

Ecco un esempio:
a:link {background: url(nuovo.gif);} /*unvisited link*/
a:visited {background: url(vecchio.gif);} /*visited link*/
a:hover {background: url(fuoco.gif);} /*mouseover link*/
a:active {background: url(attivo.gif);} /*selected link*/

Nota che l'ordine e` significativo (pero` qualche voce puoi ometterla)