The longer I go down this path of paleo-like eating, the more I am convinced that hunger is the key. I tell people, now: ultimately, this is not a battle of the bulge, fat, or weight. This is a battle over hunger and ultimately, your hunger is going to win in the long run unless you simply have the rare constitution to be miserable all the time -- like many of the calorie restriction folks do.
Fortunately, there is a solution, and that solution is to eat a natural diet of plenty of meats, fish, natural fats (animal, coconut, olive), vegetables, fruits (moderation), and nuts (moderation too). I think that the reason so many Atkins dieters ultimately plateau, stall, fail and put weight back on is that they have the wrong focus: low carb. Now, a natural diet is almost always going to be low carb unless you opt to have starchy tubers play a big role in your diet. But so often I see those who focus on low carbohydrate eat way too much processed junk (just like many vegetarians, now), much of it chock full of anti-food like unfermented soy protein, soy oil, and other heavily processed and refined "vegetable" oils. And, because it's low carb, people eat in unrestricted amounts, they tend to eat a lot of favorite junk (like diet sodas and protein bars), and they are not getting the proper nutrition
What I and others have found is that over time on this sort of diet (paleo), keeping cheating to a minimum, your hunger alters radically. At this point in my progress, it's difficult to imagine failure and regression. Why? Because I simply have no hunger for crap, anymore. Yea, I might take in a slice of pizza, now and then (can't even remember the last time, however), or a burger, but I quickly realize that I'm satisfied after only a few bites. Moreover, it can have negatives effects that turn you back the other way. During the holidays, I partook of three cookies after an evening meal of real food. Where prior to that I felt wonderfully satisfied, the whatever in the cookies made me feel uncomfortably full (now an unfamiliar feeling) for a couple of hours. Yuk.
And as far as the daily paleo eating goes, I often have to motivate myself to eat, because I simply don't get hungry at "mealtimes," anymore. Some days I'm hungry by 9 am, and some, not until 1 in the afternoon. I might be hungry for dinner at 6, but sometimes not until 9 or 10, and sometimes not at all, which is a good time to take in a fast. When I say not hungry, what I mean is that I have no desire to eat anything at all. Food doesn't even occupy my thoughts in the slightest.
I also think that if you've been eating paleo for at least a few months and you haven't seen noticeabgle changes in appetite and hunger, then maybe you need to do some fasting, twice per week, 24-30 hours each. It seems counter-intuitive, and I don't know enough to say what sorts of hormonal changes might be taking place, but I think forcing hunger intermittently plays a big role in reseting your whole hunger mechanism to a more natural state.