This has worked well for the last three years at two different companies across a number of projects.
1) Break the project into features/stories/usecases (whatever you want to call them). Features should be as small as possible but large enough to still offer business value. The customer would say with this deployed, I can now solve a problem or acheive a goal with the system that I that I couldn't before.
2) Only give estimates in terms of complexity points:
1 point - I've done this before, its a fairly simple thing. I'm confident it won't grow in scope
3 points - Not too much unknown, a bit of new thinking involved, more than a trivial feature but not something you'd lose sleep over
5 points - pretty big chunk of work, fairly complex, fair amount of unknowns
8 points - too big to estimate or even make an educated guess about, try to break these into separate features
3) Do a couple of months of work and see how many points you get Done. Done means the users have tried it out and would sign off on the features being ready for production. In production is an even better point to measure done at.
4) Calculate how many points you can now commit to for the next given period based on read data. At this point, you are probably ready to provide fairly decent estimates. You will find that your notion of what is complex or not won't change much over time. That's why this this method works.
5) Get your customers to define what it will take to sign off on the feature up front. Don't talk in terms of solutions, but in terms of solved business problems or achievable business goals. The how and the details are to be worked out durring development and with the end users and especially the developers creativitity.