Perhaps this winter is the one to blame. Batteries tend to discharge more quickly in cold weather.
To be more precise, batteries don't self-discharge faster in cold (quite the opposite), but their internal resistance rises causing lower cell voltage when the camera operates, causing higher current drain by the camera. The result is lower efficiency and thus shorter battery life. The camera could safely discharge cold NiMH cells to a slightly lower voltage than warm batteries (and they may already do so), but that probably doesn't help much because the peak currents drawn are rather high.
If you run out of power fast, I don't think it's the contacts. The circuit is either open or close, no middle grounds.
In my experience, quick discharge because of the cold is noticeable starting at -5 degrees celsius.
Generally NiMH cells should work fairly well above 0 C, below that not so much; your -5 C limit sounds right.
But there certainly are middle grounds, especially with dual AA cell cameras and their very low 2.0--2.6 V input voltage range from two NiMH cells. Try adding 0.5 ohm resistance from an external power supply and the camera may emergency shut down when you operate its zoom.
Grease, dirt and oxidation in battery contacts may very well be a reason for poor performance. There's a very good reason the battery lid has to be slid when closing it instead of just pressing it against the springs: metal to metal friction cleans up the contacts. Problem is this doesn't happen with the opposite springs deep inside the camera, at least not to the same extent.
