That would be an Internet Explorer function, not SharePoint. IE uses the
history information to determine whether you have visited the site
before or not.
To test this, have the same user load the page on a different
workstation. Obviously, he has visited the site before, but not from
that machine so the link will not be red.