With batteries, capacity (usually in mAh, miliamp-hours) decreases as current draw increases, so say you had a 100% efficient boost converter, which could convert any voltage to any other voltage, with the same power out as in - 4xAA's would last more than double the life of 2xAA's, because 4xAA's have double the voltage, therefore, for a given load current, provide half the current
As you rightly pointed out though, the greater the difference between input voltage and output voltage in a boost converter, generally the lower the efficiency. So 3V to 12v wouldn't be as efficient as 5V to 12V - but in todays standards, at your power requirements, it can still be really quite high.
Here's how I tihnk of it. Your rated capacties are 'ideal', as in, 2000mAh is pretty much the maxcimum you can expect from an alkeline battery from fresh to 1.1V (when the voltage is too low for most apps, and they are considered 'dead'). Draw 100mA from thos battery, and maths says it sohuld last 2000/100 = 20 hours. - this isn't the case, because at 100mA draw the capacity will drop. If we bring voltage into it (series batteries, same capacity different voltage) it just becomes easier to think interms of power, watts.
An alkeline AA battery starts at ~1.5V, dead at 1.1. Its discharge curve isn't 'flat' so over the discharge its 'average' voltage is probably more like 1.4 worst case. Now we have an average voltage for each battery, multiply by the capacitity to get 'mWh' miliwatt-hours. For 3 x AA's, 2 x 1.4V = 4.2V average voltage. Thats 8400mW hours, 8.4W-hours. With 4 x AA's being 11.2w-hours.
Again 'assuming' worst case efficiency for a boost converter is 75%, to boost from our battery voltage to 9V, and with a peak current draw of 100mA on the 9v load, thats 0.9W. 0.9W / 75% = 1.2W. So theoretically, with 3 AA's, 8.4/1.2 = 7 hours. With 4 AA's, 11.2/1.2 = 9.3 hours.
You made a mistake regarding using 4 x AA's instead of one
Indeed, the capaciity doesn't change, each cell is in series, so each cell has the same current flowing through it. But... that is assuming you're drawing constant current - which, with a boost converter, you're not. In a linear circuit, the battery voltage sags (so the circuit most likely draws less current) until its value is too low to keep the circuit running, then the batteries are considered 'dead' regardless of how much juice they have left. In switched mode supplies, such as boost converters,
power is converted, with power lost because nothing is 100% efficient. If you have 9V out, with a load of 100mA (0.9W) then the input current is determined by the input voltage. More cells = higher voltage = less current draw. The less current draw, the longer the battery life
That said, it should be noted that boost converters (or buck converters for step down) aren't always more efficient than linear supplies. They are more expensive, take up more space, can add 'noise' to the power lines (horrible for RF and analogue circuits) and are more trouble than they are worth if you require a 5V supply from 6V. But in your case, I think it's a great way to get 9-12V at a 'medium' current draw (0.1A - 0.4A) from a battery pack of 3-4AA cells.
I'm sorry if I've explained this badly, I tend to just rant.
If you have access to some components (as in, no need to order especially), I would be happy to post a schem of a simple boost converter with a 100-150uH inductor. Might be useful to play with to see how input current changes with input voltage given a fixed output voltage/load.