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.