Getting paid by the hour, also called working on a time and materials basis, is better for you because you always get paid for your time. Software estimation is something of a black art, and it is very easy to go awry even with years of experience. I actually use Joel's approach, which is well worth a read: Joel on Estimation
Getting paid on a project basis is better for the client... Sort of. You can estimate towards the high end to account for your risk, because it's a fact that if you work this way all the time you will eat some hours, and you can let your clients know that if you're going to assume risk you certainly can't be on the super low end all the time. Eating hours might actually be okay for you if you have low overhead and one or two really great clients that you need to take care of, but where I work my time is in very high demand and giving up hours is not considered acceptable.
I have tried many approaches over the years. Whatever you do, communicate a lot. I can't stress that enough. I will give some practical reasons for this below.
Some projects are hard to quantify or exotic and must be time and materials, at least during an initial research phase.
Speaking of which, often on a large project where the requirements are unclear, I will do an "engineering project" on a time and materials basis with a cap of, say, 20 hours, and then use that to generate requirements, a spec, and a quote. Often I am also able to do a database schema here and I sell it the whole idea to the customer as a deliverable that they can take elsewhere if they so choose, and I also let them know that during this planning phase I'm doing actual work on the project.
As for war stories, over the years I have run into a few situations where I did a bunch of hourly work for someone and, because I did not communicate constantly, things got heated. On their end, they were either legitimately surprised because I failed to set their expectations, or they were brutal negotiators and I failed to protect myself. It's really on me in any case, because I didn't communicate enough! Both situations occur, so whatever you do, communicate constantly.
One last thought: Working on a project basis does seem to be the most sure-fire way to avoid problems. Another option is to provide caps (10 hours, 20 hours) or hour ranges that things will take (5 to 8 hours). The downside is that if you constantly hit the cap or approach the high end of your quote, certain types of people will assume that you're taking advantage of them.