Turns out you can do what the top comment by chhickman is doing without any addon as well. Follow my steps above in "Edit 2", and add this to your CSS file:

    @-moz-document domain(news.ycombinator.com) {
      a:link {
        color: orange !important;
      }
      
      /* visited link */
      a:visited {
        color: green !important;
      }
    }

Per-domain custom CSS supported out of the box!