For whatever reason, I often struggle with visited link treatments, perhaps because (for me) it's often an afterthought. A color palette is selected, the page is designed -- now it's time to figure out how best to show that a link has been visited. For most sites, it's important to visually signify where the reader has been, and not everyone handles it in the same manner.

Some will tell you that changing the color of a visited link is the most appropriate treatment. I tend to use this most often, but on a link-heavy page, finding the right color balance between visited and non-visited can sometimes alter the personality of the page.
There are scores of other creative methods for handling visited links (e.g. CollyLogic, Mike Davidson and Lisa McMillan's checkbox lists, as well as any number of border/background/color combinations using CSS).
Know of any noteworthy visited link treatments? What do you think works best?