Before you rush out to buy new batteries, peeush, here's a tip which might just save your outfit some useful cash. I note that the problem arises at temperatures which shouldn't affect the battery performance too much, but only with onboard starting at remote heliports, where I presume there is no GPU to help.
Have someone check carefully that all connections in the onboard battery cranking circuit are, not just good, but perfect (that includes the contacts in any breaker/solenoid dedicated to that circuit, and is not quite as easy as it sounds).
Here's why: suppose f'rinstance that you have a 28.5 V starting motor which is drawing 50 A at full chat; if somewhere in the circuit there has appeared a tiny spurious resistance of 0.1 Ohm (that's way too small to measure with an ordinary multimeter) in some connection, it will 'drop' five of your available volts and the motor will only be seeing 23.5 V. Because a square law is applicable, that's over 30% of your cranking power gone.
Thus, a very little can matter a whole lot ..... this often-unrecognised problem is a great little earner for the battery trade .... lots of good batteries are needlessly scrapped.
A technician may be able to do a quick diagnostic check by measuring the voltage appearing at the motor terminals under (onboard!) starting load; if the result is positive (volts mysteriously getting lost) then ideally someone with the use of a good resistance 'bridge' (very sensitive measuring device) may be able to pinpoint the fault most swiftly.
(BTW, just a gut feeling, do you tend to get supersaturation conditions overnight at those remote bases?).