Generally, paying attention to the a:visited property is good. In some cases, styling the visited link is detrimental to the user experience.
Here's a comment on designer David Airey's blog:

Justin Pease, a web designer, has a link to his site. Once I click the link, it turns dark grey and loses its bolding.

This visited link style makes it blend in with the surrounding text. The only way to tell it's a link now is to hover over it, or click it.
The point of the visited link style is to show you what pages you've been to on a site. It could be a link you want to avoid, or a link you'd like to get back to. When the link blends in, it tells the user that there is no link there.
An underline on a:hover is not enough
Avoid making your visited link color a similar color to your body text. Links should not blend in, they should always stand out. Adding a hover state like an underline or color change doesn't matter, because users don't look at websites with their mouse. They use their eyes. You're asking them to guess what is and isn't a link when you could easily let them know.
Take care with your color choices, especially if you're going to remove the underline from your links. Even the smallest mistakes can make a great impact on your user's experience.





