I can offer my partial explanation why this happens. When a site wants to stylize the underline using a background property, it cannot change this property for

I can offer my partial explanation why this happens. When a site wants to stylize the underline using a background property, it cannot change this property for :visited. This includes sites trying to have a different color for the underline (CSS text decoration module 4, supported by both Firefox and Chromium now) or trying to ensure the underline do not touch a glyph (not supported natively in Firefox, CSS text decoration module 4 too) or wanting to control the width of the underline (still CSS text decoration module 4, not supported by anything). Hopefully, this will go away in the future. Some sites may also just don't see the value of distinguishing visited links from unvisited ones. That's a shame.