オレは訪問済みと認識するのに、常に"リンク文字列に下線表示"して訪問済みの場合は"下線の色を変更"するという方法をとってる(Violentmonkeyにスクリプト入れて動かしてる)
この方法でもyoutubeのようなリンク下線が表示されないサイト以外なら文字色が変わる/変わらないに左右されず認識できる
あと、これは当然のことなのかよく分からないが、リンク右クリ→リンク先のアドレスをコピーで(リンクをマウスで直にクリックしないで)開いた場合下線の色は変わらないのが地味に不便