RFC: All URL shorteners should provide a common API for returning the full URL of a shortened one.

Oops, actually they already do: when a shortened URL is requested the URL shorteners send back the redirect location with a 301 status code:

$ curl -I http://t.co/Dxl6g40
HTTP/1.1 301 Moved Permanently
Date: Thu, 23 Jun 2011 12:46:39 GMT
Server: hi
Location: http://duckduckgo.com
Cache-Control: private,max-age=300
Expires: Thu, 23 Jun 2011 12:51:39 GMT
Connection: close
Content-Type: text/html; charset=UTF-8

So what services (ie. everyone but Twitter) could do to get rid of shortened URLs is issue a request and replace the URL with the new location in case the resource has moved.

Of course, this way also URLs which are not shortened but simply have moved somewhere out of various other reasons would get replaced. Still wondering if this was a disadvantage...