I posted the Part C of this series on the SCRUM development yahoo group. There was in interesting discussion on the same in the group. The general crux seemed to be:
1. Team do not generally over estimate. If anything they underestimate. There may be some minor variations depending on recent experience of teams with some clients or features [using Atlas AJAX framework with dot.Net 2.0 takes more time] or team composition [our lead QA just resigned and new QA would take time to understand features and functionality].
2. Generally, all successful teams have a common minimum time that they would take to do a particular work. The fact that others bid lesser than this, does not mean they are able to do it in less time.
3. Sometimes, the teams might have past experience or know of a smart way to do things, that makes them able to bid lower than competition
4. Organizations can bid lower on a large project which would have many change requests and variations during the project, making up for any low bid. There may be projects where total final cost to the customer.
5. Some truly lean organizations can have low overheads and better programming frameworks like RoR which help them develop software at better quality and faster.
However, the fundamental question I am trying to answer is how do you reconcile competitiveness [quality at a price I presume] and profitability. Some of the suggestions regarding the same are as follows:
1. One is to offer a contract where the client pays per iteration. After each iteration they choose whether to keep going or stop so rather than locking them into a 6 month or whatever project they can stop if they are not happy after 2-4 weeks. That way the sunk cost is lower and their deadline is ages away so they can give the job to someone else with little problem. Usually 1 or 2 iterations is enough to convince them to keep going though. [from Dave] But none of the projects like Youtube, Google or any other successful project had full functionality in the first go. So one should underbid, but not on price but on functionality. We should do what agile does best: deliver an utterly minimal system that still meets the PO goals in the shortest amount of time. Stress the fact that they could be seeing results in as little as 3 weeks into the deal.
2. Emphasize the quality aspect of Agile teams, any past knowledge by which you can demonstrate how going Agile helped a project in the longer run would at least bring customer to the negotiating table.
The problem (or requirement) with  is that you need to orient your proposal more towards how it will help the customer to get some basic features out first. You will truly need to get into customers requirements and uncover the risks that a fixed price project would pose. Preferably you can convey that a minimal risk does exist, but you manage to tweak the requirements so that you’re really the only party that can sensibly deliver anything suitable at all. That way you don’t have to compete on equal terms on the bid.
The problem (or requirement) with  is that you need to manage knowledge internally very well. Not only should you demonstrate how your past knowledge in a field would help you suggest/ build a better product but also demonstrate how it has helped you do so in the recent past. The difference is important to realize.
Having said the above, it is also probably important to realize that not all customers are good customers and there are some you could do without. Whether or not a customer fits this bill is something that only a particular organizations context determine. On most customers, you need to work on making them understand why you recommend going Agile and T&M basis.
It is also important to have the right people articulating this message. A sales staff that can tell customers to go to hell in a way that they look forward to it is just ideal.