Based on some extensive personal experience with rechargeable AA NiMH batteries in some of my handhelds, I would agree with C:Amie: You are much better off using the lithium cells, if you can come up with a suitable way to package and charge them. It is possible to buy the 18650 cells individually, or preassembled into a rechargeable pack of the desired size.
You could try something like this "generic" battery pack:
http://www.all-battery.com/li-ion18650111v2200mahrechargeablebatterypackwithpcbprotection-1.aspx
and a charger for the battery pack, like this one:
http://www.all-battery.com/universalsmartchargerforli-ionpolymerbatterypack37v-148v1-4cells.aspx
Or buy the individual 18650 cells:
http://www.all-battery.com/tenergy4li-ion1865037v2200mahrechargeablebatteries.aspx
And a charger for the individual cells:
http://www.all-battery.com/universalli-ionplug-inchargerfor18650cells.aspx
I have had fair to poor results using Energizer brand NiMH AA rechargeable batteries in my little Zaurus ZR-5800, my Sharp Mobilon HC-4100, and my Casio Cassiopeia A-20. Those are all very low-power devices. Yet the NiMH rechargeables, being rated at only 1.2 volts and 2450 mAh, drain so quickly, it's not even worth the trouble. In fact, the A-20 sometimes won't even turn on with them.
Dan