BTW, one more service: BudURL.com
Its awesome. Actually its got all the features that cli.gs (the best of 5 you have reported) has, and on the top, it lets you create custom URL like budurl.com/ycombinator than a random letters.
2nd big advantage is: its a decent domain name, than cli.gs - I can tell that to someone over phoe without them asking 'What?', 'Can yo spell that?'
Most of these services create a permalink, but they should offer a choice. Sometimes I create a temp link, which I don't need afterwards. Why can't they let me reuse the same URL and or just let me delete it? I don't want something of no use to any living being in the world occupying some space in a database, and in turn making the URL fetch somewhat slower.
URL shrinking is a funny little business. With the right implementation, your product only gets worse as it gets popular (and the URL's get longer).
If I were running one of these, I would focus on buying as many short domains as possible and getting people distributed across them to counter the effect.
One more point: Found out today that, you can redirect using some service (bit.ly for one) and get your traffic tracked! And one of them (decenturl.com) make a meaningful url instead of tinyurl.com/sUw7_gKj. I think these are nice value additions.
I use mostly is.gd, haven't had any problems yet. It's also the shortest :)