I guess I didn't explain myself clearly... if you shortened the url yourself (I'm sure you can find a good implementation of this), why not name the S3 image exactly the same as the short url?

In the example you gave elsewhere, the image would be http://billr.s3.amazonaws.com/J7W5uY instead of http://billr.s3.amazonaws.com/01C03E08-4CFD-4709-87C9-BB60FD... - so bit.ly wouldn't be needed.

The suggestion elsewhere in this discussion to encode the entire bill in the url is probably the optimal solution though. With a bit of caching it's probably the cheapest you could run your system (sans S3).