I'm still in the "all unvisited hyperlinks should be blue and all visited ones should be purple." camp. It's simple and everyone knows what to expect!
Your mileage may vary. I've also had folks cite usability experts who suggest that changing navigation options is a Very Bad Thing. I do it when folks go to the purchasing page. It is a Very Bad Thing That Pays My Rent And Then Some.
I've managed to use Lotus Notes, too, that doesn't mean I think it was a good idea.
It's good to be consistent. But lots of sites now have an colour scheme that makes it clear which links are visited and which ones are unvisted. Generally the visited ones are a duller / subdued.