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
Kudos to TheMadExile who answered this question on Twinery.org forums.