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:

• Does a flash work well with regular alkaline batteries?
• What attributes should I look for when buying batteries for a flash?

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 ;)