Usa la regla LoVe-HAte (Link, Visited, Hover, Active). El orden es
importante:
a:link { ... }
a:visited { ... }
a:hover { ... }
a:active { ...}
De esa manera, las propiedades de :hover se aplican después que las de
:visited y prevalecen. También puedes usar el !important, como te han
comentado.
Saludos,
Ramón.