I think I can speak to this a little bit; I've taken four points off my BMI in the last year or year and a half or so, all through counting calories in and calories out... and I'd rate the experience as slightly easier than trying to breathe a little less.
The most annoying part was that everyone... fat people and skinny people would give me a hard time for actually tracking everything I ate. "Just eat less," they'd say, along with some advice about how they have a friend who lost weight on some fad diet that restricts not how much you can eat but what you can eat. I had a doctor who told me to take the sides I'd normally eat and cut them in half, you know, like I planned my meals or something.
For me? writing down what I ate was key; Obviously, (and this is likely the genetic part) some people have something that causes them to be not hungry anymore after they've eaten enough food. Whatever that is, it's obviously not working properly in me, or else I never would have gotten fat in the first place, so I need some external tracker to figure out if I've eaten enough.
(The other thing that seemed to be different about my experience than about most people's was that if I went a lot below my maintenance caloric intake, say, significantly more than 40% below for several days in a row, my work performance would collapse. If I tracked my caloric intake and kept it around 25% below what I burned, i was okay, though it was still difficult.)