Das Alles-rot-Script hat funktioniert.
Weder userContent.css noch das Add-on "Stylus" unterstützen Pseudoklassen für Links (alle Links, egal ob schon besucht oder nicht, werden wie a:link behandelt, keiner wie a:visited); anscheinend liegt das daran, dass Gecko das Besucht-Attribut erst spät behandelt – ich habe schon gesehen, dass auf den Seiten von anderen Nutzern, die für besuchte Links eine abweichende Färbung verwenden, diese erst angewendet wird, nachdem die Seite fertig geladen hat.
__
P.S.: Offenbar ist es noch komplizierter. Aus Datenschutzgründen werden für besuchte Links nur spezielle Stiländerungen unterstützt.