Well, as long as you wire them in parallel (as you have been), adding more batteries will decrease the load on each individual battery, and the circuit will last longer while still providing 9V. For example, 2x9V in parallel (assuming 1000mAH [milliamp/hours] per batt) = 2000mAH at 9V - that's 2000 miliamps (2 amps) for a period of one hour. (My numbers are just pulled out of the air, so don't follow my instructions verbatim.)
A linear regulator is more wasteful (of energy, in the form of heat) than a switching one would be - but is cheaper, and generally smaller. See what kind of life you get out of the 2x9V setup, and if that doesn't work for you, put another 9V in the circuit.