Marc,
If you are leaving the lasers constantly on, it will juice out the batteries pretty quick. 30min constant on time is pretty good for a 5mW unit. Lithium Ion will probably not be much better in cold weather. You might try a nickel metal hydride battery though. I'm not too familiar with this chemistry but i believe it has better cold temperature performance than LiIon. The energy density is not as good but they may last longer in the cold. If you really want outstanding cold temperature performance, go with nickel hydrogen. Performance in this chemistry actually improves as temperature drops. Unfortunately, the smallest single cell I am aware of is about 2.5 amp hours in capacity and looks nothing like a AAA cell, and, oh yeah because of the platinum catalyst and space rating, will cost about $10,000. It will last over 20 years though!