The first problem -- URLs can vanish -- looks like it may be solved soon. Many URL shortening companies are escrowing their databases of shortened URLs with the Internet Archive, an honorable, established nonprofit. If the companies go bust, their URLs will be redirected to the Archive and thus persist.
The non-profit Internet Archive, a digital library with extensive text, audio, video and web collections, will administer 301Works.org as a project of the Internet Archive. "Short URL providers have in the space of eighteen months become a corner stone of the real time web -- 301Works.org was conceived to provide redundancy so that users and services could resolve a URL mapping regardless of availability. The Internet Archive is a perfect host organization to run and manage this for all providers," says Bit.ly CEO John Borthwick. "The Internet Archive is honored to play this role to help make the Web more robust," added Brewster Kahle, founder and Digital Librarian of the Internet Archive.URL shorteners working with Internet Archive for long-term preservation (via Kottke)
All participating companies are members of the 301Works.org Working Group, a technical and policy discussion group, but the Internet Archive will manage the over all initiative in a fashion consistent with its charter as a non-profit organization, and supporting the interests of the greater community ahead of those of the participating companies.
Participating companies will provide regular backups of their URL mappings to the 301Works.org service. In the event of the closure of a participating organization, technical control of the shortening service domain will be transferred to 301Works.org in order to continue redirecting existing shortened URLs to their intended destinations.