You can get Lithium AA batteries that are 1.5v the same as normal AA batteries. Argos do 2 for £5.99. They last a long time in use(high capacity), they have a long shelf life, they are lighter than normal batteries, and are the least affected by low temperatures. But they are also the most expensive - by quite a bit. They are ideal as a set of emergency batteries, you can keep them in your pack for years and when you really need them they will be good.
But Nick wanted rechargeables. Nickel-Metal Hydride (Ni-MH) rechargeable batteries don't have the memory problems that Ni-Cad batteries have. You can buy them in capacities from 1300mAh output to 2300mAh, (that's milliamp hours) - the higher the better. The high capacity ones are designed for high draw appliances like digital cameras or halogen lamps, but they don't say this on them. They are less affected by the cold than normal, non-rechargeable Alkaline batteries, but not quite as good as Lithiums. They will work out a lot cheaper in the long run, although the initial outlay is large if you want high capacity batteries and a charger that will do the job quickly. But then once you have the charger you can use rechargeables for everything else too.
So I would say that Lithium batteries are not the way to go - except maybe for an emergency set. Ni-MHs will do nicely.