Agile in a Fixed-Price Environment

My organization works with some very large customers who have complex procurement processes in place with budgetary approval and purchase order sign-off needing to go through multiple departments before work can actually begin. They like to know how much a project is going to cost up-front and they expect to be billed for that exact amount.

This presents some challenges for a software house operating in an Agile manner. Think about that for a second. You want to deliver software to your customers in short iterations to gain early feedback and then push that feedback into future iterations - but this can affect the overall (fixed) cost of the project that was agreed up-front. How do you handle that situation?

For me, there are a number of possible solutions:

• Fix project price, but flex on project scope. Go ahead and draw a financial line in the sand, deliver in small iterations and get the feedback you need. If the feedback you receive affects project scope to the point where you can't or don't want to absorb the cost internally then go back to the customer and discuss which areas you can sacrifice that are of lower priority in order to make the changes received through the feedback. This can work, but clearly you're going to need customer buy-in up front. This may prove unpalatable to customers who have a feature list that comprises solely of 'must haves'. 
• Use Agile internally and present a waterfall exterior to the customer. This can work (to some extent). You can develop release quality, working software each iteration...you just don't release it. Obviously you don't get the early feedback, which is a major drawback, but I still think it's better than running a 6-month project only to find at the end of the 5th month that you're not going to deliver, or can only 'deliver with caveats'.
• Fix project price and scope, but include contingency for re-work following iteration feedback. Many large organizations are used to working with a contingency pot for mid-project change requests. Include this 'pot of money' in the initial estimate with the expectation on both sides that it will be used.
• Fix project price and scope and be prepared to absorb all additional costs internally. This doesn't sound cost-effective (and it probably isn't) but you might choose to do this if you believe that developing in an Agile manner will yield other commercial benefits either for this or subsequent projects.

Thoughts?