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.