Jeremy Miller recently tried to "answer hard questions about Agile development". One question he didn't really answer was that of agile and fixed bids :

"I don't really think the Agile answer to a fixed bid is any different from any other process.  I do think that Agile practices and project management can give you far more control and feedback on the "Iron Triangle" of resources, time, and features"

Jeremy says that this would enable the team to fail "softly" (i.e with some functionality etc.).
I think (well, actually, I know since I did that) we can do better than just use Agile and hope for the best. For instance, here are a few  strategies I successfully used:

1. Pre-budget the whole project with rough milestones and estimates (works best if you have prior experience in the domain)
2. Coordinate expectations with the client and trade - the single project to many smaller ones. What I did was to get a blanket purchase order for the estimated amount and each smaller order/project  "ate" some of that budget until it was done.
3. Since the project was for a CMMI level 3/ ISO 90003 we also added a few documents to the backlog - and let the product owner prioritize them vs. deliverables. For instance the "Architecture document" was delivered after 6 iterations when the architecture stabilized
4 exchange requests instead of change request - new functionality comes instead of old promised one

Of course we also did the other SCRUM practices of releasing frequently, demonstrating progress, retrospective etc.

I would love to take credit for the ideas above - however, Pascal Van Cauwenberghe details most of them (and more) in two papers called "Agile Fixed Price Projects part 1: The Price is Right" and "Agile Fixed Price Projects part 2: Do you want agility with that" (go read them..)