I've actually tried this on the main site, but it was not so successful. Mostly because the links are shortened, and I don't have the capacity to unshorten every link (most computation is done client-side anyway), and programs like VigLink don't look at short links either.
Have link HTML printed out as per normal, attach JS that routes every clicked link through your servers. E.g.
This is a twitter <a href="http://bit.ly/blah"
onclick="document.location='http://yourservers.com/follow?url=' +
escape(this.href);return false">link</a>.
That way you can look up the Twitter links only if they are clicked and any slow down happens after the click, not before display.
As a bonus you get to see what links everyone is clicking as well.
You'd likely need to roll your own mini-crawler to dig out the shorten links, and where applicable, create new ones and replace them. Questionable indeed.