Zdefiniować dla odwiedzonych i nieodwiedzonych linków identyczny zestaw reguł.
Wasacz ma rację. Musisz zdefiniować jednakowe style dla tych typów. a:hover nie ma nic do tego i musi działać.
Niestety nie dałeś żadnego kodu, więc trudno jest coś wywnioskować, ale według mnie nie działo ci to dlatego: