Do You Always Need to Change the Color of Visited Links?
Do the links on your Web site need to be colored differently depending on whether a visitor has already clicked on them? If you read a lot of Jakob Nielsen, you’re probably tempted to say yes. Indeed, in Nielsen’s 2007 update to Top Ten Mistakes in Web Design, “not changing the color of visited links” is sin number three.
But the problem with one-size-fits-all usability guidelines like these is that they tend to overlook the fact that not all Web sites are created equal — or, in this case, that not all hyperlinks are equal.
When It Makes Sense: Links to Pages
Nielsen’s refrain makes sense when sites uses the traditional “page” model, which was the dominant model in 1996 when Nielsen originally warned about changing standard link colors. In this model, selecting a link takes you to a new page of information. When, as a visitor to a site, you’re presented with lots of links to lots of pages, it’s certainly helpful to be able to see which links you’ve already selected.
Forums, news sites, and other content-heavy sites are good examples of this.
Where visited link colors are helpful: Jakob Nielsen’s own useit.com:

Where visited link colors are helpful: Hacker News forums:

When It Doesn’t Help: Application and Persistent Navigation
These days, links don’t always point to pages of content — especially not when the links are in the context of an application. Likewise, links aren’t always in a sea of other links — they may be part of a clear set of links used in persistent navigation.
In the application model, the Web site (or part of it) is an application rather than a collection of pages. Links on applications often trigger actions rather than accessing new content.
For instance, a photo sharing application might feature a link to rotate a photo, one to delete the photo, and another to get the original photo. Changing the color of the “rotate” link after a user rotates the photo doesn’t impart any new information. The user doesn’t need to know on subsequent visits that she has rotated the photo before.
If anything, changing the link color here could prove to be confusing because the user might question why one of the options — rotate — looks different visually than the other options.
Where visited link colors would not be helpful: Kinverge photo toolbar:

In persistent navigation, the links may point to content pages, but the limited number of options and the fact that they are constant diminishes the benefit of changing the visited link color. And again, changing the visited link color here may even increase confusion.
Where visited link colors would not be helpful: Amazon.com navigation:

Visited link colors can make things even more confusing when you have a limited number of nav links and are already using a different style to indicate the visitor’s current position. Using three styles for, say, five links creates visual clutter and makes it hard to distinguish what the different styles are for.
Where visited link colors would not be helpful: Clicky dashboard navigation:

It’s All About Context
This is not to say that all links on your site or application should be one color, or that visited link colors are only for content-rich sites. But do you always need your links to show a “visited” state, as Nielsen would have you? No.
The best solution is to pay attention to context. Chances are, any Web site you build these days is going to have a mix of content and applications, with some persistent navigation tying it together. It may be that what works best for your audience is to give each of these classes of links a distinct style and to only set a unique visited color for the content class.
Now, that may violate another of Nielsen’s guidelines (regarding consistency), but that’s an argument for another day.
My name is Amit Asaravala. I'm an Internet technologies consultant & Web developer located in the San Francisco Bay Area. I specialize in helping organizations build great Web sites on open source technologies.
Jakob, himself said all this in 2004 in a guideline for visualizing links. This was linked from the very article you referenced.
http://www.useit.com/alertbox/20040510.html
Colin, the 2004 article talks about exceptions for underlining links in navigation, but it still asserts that “The color for unvisited links should be more vivid, bright, and saturated than the color for visited links.” Can you point me to where Nielsen allows for some visted links to be the same color as unvisited ones?