Short answer:
- get yourself some good, rechargable NiMh-AA with low self-discharge (see extensive list here on Wikpedia), at least two sets
- buy a good recharger with discharge-function and peak-detection (delta-Voltage) like the Technoline BC 9001
Longer answer: you asked for energy-solutions people use for flashes: see the linked (and recommended on the side of your question) threads:
and you'll be recommend NiMh-accumulators anyway. So buy yourself some sets of decent AA cells, like Eneloop (reducing self-discharge) and a decent charging device (I like my BC900) using an delta-U (peak) detection.
Your problem most certainly is not that AA accumulators "go out or low" but that your energy management is currently bad. If you (mis-)use an old or bad lithium accumulator, it will go out too (and that even faster). It is the same with your accumulators as with your memory chips: handle with care.
Of course the circular AA never will have an energy/mass-ratio as high as a proprietary lithium-ion, but I find this neglectable with big cameras. Most LiIon-accumulators have all the tech for preventing deep discharge and regulating charging packed away, but that is because they are more vulnerable (and tend to answer abuse with a bang) and because of that they cost more.
The bonus on AA is:
- you'll get replacement-accumulators anywhere on the world
- there are some solar chargers too, if your trips really take this long
1 I use it for my Canon-compacts for >= 5 years. The money for a better recharger is a good investment, this unit eat 12V, has a 110-240V adapter with changeable plugs and a car-adapter. Reads as "usable world wide".
Edited: mellowed the answer, thx @lindes ;)