Best battery for low power, long term application
Total energy per day (Joules=AmpsVseconds/efficiency*reps/day) (40x4+200x1)*5.5*30/0.85 =70J/day, 25kJ/year,11kJ/5 months. 

If you only get to recharge after 5 months, why use rechargeable at all if the energy is low? D-Alkaline=75kJ, AA=10kJ (55C max) (alkaline shelf life 5 years) or lithium-irondisulphide duracell AA (1.6V, 10kJ) 60C max ( shelf life 20 years)

Alkaline performance is excellent at 50C, (poor when cold) Shelf life will be hugely degraded at 50C of course, but still manages 50% at 5 years see fig 15, self discharge graph
In your case the choice of cell size is about peak current at lowest temperature, not capacity.

I think your understanding of lithium rechargables is not quite right: To maximise the energy stored in them, they are recharged to a terminal voltage. The higher that is, the more energy you can get, but the more damage you will do. 4.3V = short life, 4.0V = long life. 
NiMH batteries have also improved with versions called LSD - low self discharge, which gives shelf life to 2 years.

An arrangment with 3 cells and stepup to 5V is good for this sort of job. A small micro can run directly from the batteries (2.7-4.5V) without needing the switchmode, to keep track of sleep time etc. A (cheap) stepup, with poor idle current can be turned on for transmissions.

See also this answer to a similar question

Use a tiny solar panel (1" square, 40mW) to stretch out the alkalines life if you want. 70J/day / (3hoursSunPerDay *3600secs) = 6.5mW. An alkaline may last years with solar float charge