You could introduce an 'intermediate' script...
Rather than each of your links poiting to the other sites URL, you could point to a php script (on your site), with the URL of the external site in the query string. The php script can then log (to a text file, database, etc) the user and the name/id of the site, and then redirect the user (using header("Location: ...")) to the actual site.
Of course, this would mean:
a) that the user would actually have to visit the site before it is flagged, they couldn't just flag multiple links in one go
b) That you would need to identify the user for subsequent visits, so that the log you keep can be referenced by some unique method. To do this, I guess you could either store some kind of unique id in a cookie, or introduce a login/password mechanism.
Maybe a bit too complicated for what you want?
Of course, the easiest alternative is to declare a CSS that formats a:visited links differently...
Dan