Read over the FAQ. This is basically the service I wanted to create with Bit.ly when we started it up in the summer of 2008. But it's apparently missing one key component, the freedom to switch to a different service. Once you've chosen to map a domain to bit.ly, if you map it to another service, all the links you created with bit.ly break.
There is a way for them to provide the ability to switch, Joe Moreno at Adjix did it. Bit.ly could echo all your shortened URLs to an Amazon S3 bucket that you control (and pay for, btw). If you decide to switch, just change your CNAME to point to Amazon. Or give it to a competitive service that you like better. This protects your choice, and protects all of us if Bit.ly should fail.
8/19:09: How to Fix URL Shorteners.