¡Hola Amigos!

Este código sirve para hacer eso que dice el título. No se olviden de incluir dojo en su script para que esto funcione.

Edición: Para aquellos usuarios que solo estén interesados en lograr la funcionalidad, y no les importe estar familiarizados con el funcionamiento interno de este asunto, dejo a continuación un enlace a una librería que lo hace todo por nosotros: Social History Javascript

<style>
a.checkme            { color:#00ff00; }
a.checkme:visited    { color:#ff0000; }
.highlight            { background:#fffea1; }
</style>

<script type="text/javascript">
(function(d,$,$$) {
    d.ready(function() {
        d.connect($('tell-me'),'onclick',function() {
            var sitesFound = 0;
            $$('a.checkme').forEach(function(node) {
                var color = d.style(node,'color');
                if(color == '#ff0000' || color == 'rgb(255, 0, 0)') {
                    d.addClass(node,'highlight');
                    sitesFound++;
                }
            });
            //output stuff
            if(sitesFound) {
                alert('Te encontre en  ' + sitesFound + ' ajaja que bueno');
            }
            else {
                alert('Nada que ver');
            }
        });
    });           
})(dojo,dojo.byId,dojo.query);
</script>


<ul>
<li><a href="http://css-tricks.com" class="checkme">CSS Tricks</a></li>
<li><a href="http://snook.ca" class="checkme">Snook</a></li>
<li><a href="http://cnn.com" class="checkme">CNN</a></li>
<li><a href="http://digg.com" class="checkme">Digg</a></li>
<li><a href="http://flickr.com" class="checkme">Flickr</a></li>
<li><a href="http://php.net" class="checkme">PHP.Net</a></li>
<li><a href="http://reddit.com" class="checkme">Reddit</a></li>
<li><a href="http://yahoo.com" class="checkme">Yahoo!</a></li>
<li><a href="http://google.com" class="checkme">Google!</a></li>
<li><a href="http://msn.com" class="checkme">MSN</a></li>
<li><a href="http://gmail.com" class="checkme">Gmail</a></li>
<li><a href="http://imdb.com" class="checkme">IMDB</a></li>
<li><a href="http://mootools.net" class="checkme">MooTools</a></li>
<li><a href="http://jquery.com" class="checkme">jQuery</a></li>
<li><a href="http://wordpress.org" class="checkme">Wordpress</a></li>
<li><a href="https://droope.wordpress.com" class="checkme">El blog de drope</a></li>
<li><a href="http://dlisted.com" class="checkme">DListed</a></li>
<li><a href="http://foxnews.com" class="checkme">Fox News</a></li>
<li><a href="http://dzone.com" class="checkme">DZone</a></li>
<li><a href="http://nettuts.com" class="checkme">NetTuts</a></li>
<li><a href="http://youtube.com" class="checkme">YouTube</a></li>
<li><a href="http://diggnation.com" class="checkme">Diggnation</a></li>
<li><a href="http://collegehumor.com" class="checkme">College Humor</a></li>
<li><a href="http://facebook.com" class="checkme">Facebook</a></li>
<li><a href="http://myspace.com" class="checkme">MySpace</a></li>   
</ul>

Es algo tan sencillo como inteligente: Mira de que color colorearía un browser un enlace, y a raiz de eso determina si existe en el historial o no.

¡Tiene muchos usos potenciales!

Espero que (no) les sea de utilidad.

Un saludo,
Pedro