It really comes down to personal preference. Do the workout you're going to be able to keep doing.
The body is a complex machine, and "calories in, calories out" is an over-simplified way of looking at energy usage and storage. I hope you didn't write off the T-Nation article just because it's a bodybuilding/musclehead website. There are actually some very good tidbits on why things that don't burn tons of calories themselves end up having a significant effect on weight loss. Of particular interest may be the effects that HIIT regimens have on EPOC.
For context, I have done both steady-state cardio and HIIT before and saw good results from both, even though I have always been of slight stature. Currently, I do Mark Rippetoe's "Starting Strength" barbell program, and, despite eating absurd amounts of food to fuel the increases in strength I'm making (generally eating at a 700-1000 calorie surplus), I have gained very little fat. It's like the T-Nation article says: the most effective weapon against fat loss is correct nutrition.
I didn't say exercises, I said activities. Sprinting will actually build muscle, jogging 20 miles will not. It is a difference in how your body adapts to the stimulus.
So, with that in mind, no, cardio typically is not a good choice for people with what 80% of people are hoping to achieve. Put plainly, the time/reward tradeoff is just too low. Sprint, bike sprint, row, swimming, they are all better than the elliptical, typical running and the like.
http://www.drkehres.com/2009/06/sprinters-versus-marathon-ru...
If you are a world class marathoner and are running 6 minute miles for a marathon, you will probably have some muscle and look pretty lean. That being said, 99% of the world is not this and are basically working out for hours with very, very little benefit to the time. However, even a recreational sprinter is going to see huge benefits from sprinting in both muscle building and fat reduction.
The likely reasons you kept gaining weight while running, pick one or multiple:
- Not running as often as you lift, so the total calories burned per week (or month) was lower.
- Running too slowly so that your heart rate didn't get up to the point where you were really working.
- Ramping up your carb intake, whether consciously or subconsciously this is really common when people start running -- your body starts craving carbs. Which then results in a calorie increase, which is the real problem (not carbs themselves.)
- Policing your eating better while lifting.
Ultimately if you want to lose weight you have to not only exercise but also keep your daily calorie budget at a deficit. People who have trouble losing weight usually fail at the latter one.