We have a long running Agile project underway. Every month or so we deliver a new release, then work with the customer to decide what will be in the next release. Unlike many Agile shops, this isn't our only project - we have other small software development projects, mentoring work, and so on that take up about two thirds of the team's time, leaving one third for this project. What's more, we do this as a little fixed bid project every month, and both my bottom line and the customer are happy with the cost of each release. The key to that, of course, is accurate estimation of the effort in each iteration.
In some ways we have it easy now. The client has working code, and each month all we need to estimate are the changes and additions to that code. But how would it be if we were starting from nothing and planning to build a whole big system over the course of a year or so, for someone who wanted a fixed cost up front and a reasonably complete list of features to be delivered for that cost? Stephen Forte gave a talk recently on just that topic. Plenty of good ideas and a fun listen.
Kate