So if you thought that the last post dates me, see here. This is from the mid eighties, magnetic stripes to save stuff on. One stripe held all of 1.2 kb. What fun to remember!
There is an approach in URL shorteners that I have not yet seen, but think that has some merit: Store all the information for the URLs in a DNS zone. Store the URLs you point to as TXT records. The zone can then be pulled and perused at will. That way, data is never stored in just one companies database, you can just go in an pull those links that interest you. If the shortening engine then allows for user specific zones, you can just get to all the data you are interested in.
The prototype should not be so hard to get in shape.