Those aren't exactly true.
What you are looking for is a High Current to get a fast response since it's the current that magnetizes motors, and not voltage. To get a high current, you need a battery with a high discharge rate. For exemple, you can get bigger cells in Ni-Mh or get a high "C" count Li-Po battery. Voltage by itself is not really relevant, you can get a 7.4V Li-Po that will outperform a 8.4V Ni-MH.
For the mAh (milli ampere hour), think of it like a gas tank in a car. The bigger the gas tank, the longer your car will run when it's full. But it's won't be more "powerful" or anything, it is just a storage count unit. So, a battery with twice the mAh will last about 2 times longer for the same voltage/amperage.
If you are looking for Li-Po products, and can rewire your batteries (very easy to do if you have a soldering iron at home), check your measurements and consider those:
They are cheap and really good batteries, they are meant for the RC world, but a battery is a battery. If it fits, it's good.
If you are looking for "Deans Ultra" (NOT the mini connectors), get those: http://www.dealextreme.com/details.dx/sku.10788
They are 10x cheaper than the real thing and will perform the same. The red plastic is plastic here and the real deans are nylon but if you are careful when soldering (not leaving your iron on the metal for 30 seconds), you will be fine.