Do you want to lose weight or do you want to be fit? I've been frustrated in the past by the fact that my body doesn't look like the North American female ideal, but I think of the number of hours I put into exercise compared to some of my skinny but sedentary peers, and I'm sure that's going to make a difference in future health. I think it's generally accepted that exercise improves health INDEPENDENT of weight. (I should try to cite this but I have a midterm in an hour... If you want, I can do more in-depth research when I have time.)

BTW, exercise didn't lead me to lose any weight whatsoever, even when combined with an attempt at the paleo diet (albeit not one that spent lots of money, or involved a personal trainer).

I think that's true for most people. Exercise seems to be better for maintaining a given weight than for losing weight.