I once read that 40% of the population is "immune to exercise"

If you mean, 40% of people don't lose weight by exercising, that's probably correct. The OP said "basic level of fitness", though, which does not necessarily mean weight loss.

I currently walk a couple of hours every other day. I have no idea whether this does anything (besides exhausting me so much I don't get any work done for the rest of the day, of course).

There is a fair amount of study (for citations see "Body By Science") that longer exercise does not result in greater health gains, and that it is rather the intensity of exercise that makes the difference.

In my own personal experience, long walks are pleasant, but I felt a greater increase in energy levels from using one of Sears's 10-minute PACE workouts (1 minute walking, 1 minute all-out running, repeat 5 times, then cool down). A few days of this and my general energy levels throughout the day went up. (I would guess the OP's suggestion of hill sprints is based on the same principle of alternating high intensity and low intensity activity for a short period.)

There are quite a few ways in which conventional or popular wisdom about exercise is wrong; the idea that more exercise is better is one of them. (The idea that exercise will help or cause you to lose weight is another.)