La pseudoclase :visited tiene limitada su funcionalidad en la mayoría de los navegadores por razones de seguridad, creo que actualmente solo opera te permite la personalización.
Aqui hay una página con multiples variantes para testear
http://webdesign.maratz.com/lab/visited_links_styling/
Saludos