Por ejemplo si tienes dos listas, se puede con
class (
<li class="lista1"><a>...</a></li> y
<li class="lista2"><a>...</a></li>), en el CSS pones:
li.lista1 a:hover{...};,
li.lista1 a:visited{...}; y
li.lista2 a:hover{...};,
li.lista2 a:visited{...};.
Saludos