Tinyurl has ads, but I wonder how effective it is. People can avoid going there altogether since they provide an API. As do most other services. Simply making use of that API in your own services, software means that their number of page views doesn't increase.

Now, it may get annoying, but having a "You are redirecting to http://somelongurl.com" sort of page, would not only be safer for all, but would also provide another spot for ads. (I know one of the services does this already, but I dont' remember which one)