firefoxであれば、about:config から layout.css.visited_links_enabled で検索してみてください。
値が false になっているのではないかと思うので、true に変更してください。

※ もし既に true になっている場合は、申し訳ありませんが原因がわかりません。

お役に立てず申し訳ございません。
検索してみたところ、訪問済みか否かは履歴を記憶・保存しているかどうかで決まるようです。

プライバシー → 履歴 の「履歴を記憶させる」または「記憶させる履歴を詳細設定する」に設定し、「表示したページとファイルのダウンロードの履歴を残す」を有効にしているか確認してみてください。

また、コンテンツ → フォントと配色 → 配色設定 で未訪問と訪問済みの色が同じ or 見分けづらい色になっていないか、念の為に確認してください。


これらも問題ない場合は、申し訳ございませんが詳しい方の回答をお待ちください。