Allegedly a:visited doesn't work in any story format. 
If you are using SugarCube you can use a trick. 
Step 1. Enable visited link tracking with config.addVisitedLinkClass. Just create a script passage with the line
    config.addVisitedLinkClass = true;
This will start appending the link-visited CSS class to visited links.
Step 2. Add a stylesheet passage setting 
    a.link-visited {
       color: purple;
    } 
Kudos to TheMadExile who answered this question on Twinery.org forums.