We set up 2 or 3 estimation sessions with the potential customer and our developers where we discuss the work at hand and set the acceptance criteria. The developers estimate the work in story points during the meeting.
Afterwards we sell the customer a number of story points. This is possible because he has a good idea of the value of the story points. We tell him that he has the possibility to fine tune his backlog/scope during the project and that it will be easy due to the use of the story points. We also tell him that there will be a frequent delivery of working software so that he can monitor the progress and get new insights.
By agreeing on a number of story points the customer is guaranteed to get value for his money. If he doesn't change his backlog he has his fixed price/fixed scope project, but my experience is that he will make changes. By doing the estimations in the presence of the potential customer we try to build a relationship based upon openness and trust.
We managed to convince clients like you describe, who "want a budget and a deadline", and they were happy we wanted to really understand what they needed, instead of working from a document. We showed that we wanted to invest in these projects.
During the estimation sessions we estimated their entire backlog. This gave x story points. We suggested to add 25% for those features that weren't yet clear or known at the time. With the estimated backlog attached to the contract they were reassured that they would get everything for the fixed budget.
Originally the bid was time and material. As they wanted to have a fixed price bid, we suggested to work for the price we gave them and use the 25% extra story points for contingency. If things went well, the part of the 25% that was not used to cover the delays we encountered would be used to deliver more functionality for the customer.
This stimulated them in a number of ways: first, they did everything they could to enable our developers to work as fast as possible, as this was clearly in their own interest. We never had to wait for answers to questions. Secondly, they really understood the concept of the story points. Before the project started, they had already removed some of the stories and asked us to estimate other stories. No complicated contract negotiations were needed for this.
We kept them informed of the progress and kept a very open communication. They got a progress report every 2 weeks: x % of the story points done in y % of the estimated time leaves z % of the extra story points available. We had a bit of a difficult start but managed to catch up with the estimates by the end of the project, which left 100 % of the extra story points available for extra development. The customer was happy because he got everything he really needed (and that was a bit different from his initially requested features, he removed some and added others).
The customer was also happy because everything was delivered in the foreseen timeframe (where he also did everything possible to help us like chasing tickets, answering questions immediatly, involving the users in weekly analysis meetings and also involving them in functional testing).
My company was happy because we delivered in time and on budget. My company was also happy because the success of this project opened the door for more projects. We even got mentioned in the monthly magazine of the customer that was sent to people worldwide.
Doing good estimates was the most difficult part of the project, but having the estimation sessions up front helped us to understand the difficulty and the risks. It enabled us to give an estimate based upon facts and removed a lot of the unknowns.