I use lithium batteries exclusively, up to ten times the life and I can leave my Petzl and my Garmin in the car throught the winter. I do not use rechargeables because of their shorter shelf and use times.
Lithium batteries perform better than NiMH (and even better than alkaline) in the cold. However, in the warm all three technologies perform similarly for GPSes.
I have used NiMHs very successfully down to temps of 5-10F in my (medium drain) headlamps and GPS. (I generally use NiMHs with NiMH and/or lithium backups.)
In the warm:
* All three battery technologies have similar capacities (~2500 mAh).
* GPSes consume ~100-200 mA (medium drain) which all three technologies handle well.
* Lithium and NiMH handle high drain devices (eg digital cameras) well, alkaline poorly.
So the significantly greater lifetime of lithiums only occurs for high drain devices and/or cold below ~5-10F. (Note: the effective capacities of all cells decay gradually with decreasing temp rather than a sharp cutoff.)
See
http://data.energizer.com/PDFs/l91.pdf (AA) or
http://data.energizer.com/PDFs/l92.pdf (AAA) for more info.
Rechargeable cells, in addition to being cheaper over the long run, have the advantage that one can always start with fully charged cells without accumulating a stock of half-used non-rechargeable cells...
BTW, some older electronics (including GPSes and headlamps) can be damaged by lithium cells. (Very fresh cells can put out up to 1.8V which is too much for some devices. The voltage tapers fairly rapidly so one can sometimes bleed off the peak voltage in a tolerant device before using lithiums in an intolerant device.)
Doug