innanzitutto ti conviene scrivere le pseudoclassi in un file esterno alla pagina e non stare a scrivere (e modificare, eventualmente) pagina per pagina. Poi...
la gerarchia corretta x le pseudoclassi è:
a:link;
a:visited;
a:hover;
a:active;
detto questo, passiamo al tuo problema.
Devi crearti una classe per ogni colore o tipo di font che vuoi nella pagina; poniamo il caso che tu voglia un link verde; nello stato visited il colore è rosso, e nello stato hover passi a nero e sottolineato:

.nomeclasse a{
color:green;
text-decoration:none;
}
.nomeclasse a:visited{
color:red;
text-decoration:none;
}
.nomeclasse a:hover{
color:#000;
text-decoration:underline;
}
adesso devi applicare tale classe ai link che vorresti vedere
visualizzati con queste caratteristike.
la stessa cosa devi fare per tutti gli altri link che vuoi distinguere da questi. Spero di essere stato kiaro.
Facci sapere come va.
Floyd