It could be free if it was written on AppEngine, and it stayed within the "free" quota.

(For the record I know TinyURL.com was not, but i'm pointing out that a newer/similar service could be.)