Try moving up to the newer low self-discharge NiMH like the Sanyo Eneloop. Some of your problems may be related to the NiMH battery staying in a discharged state for an extended period of time and the low self-discharge rate of these new batteries helps combat that. However, I'm with you, I always keep a set of alkalines, or better yet, lithiums, handy just in case.

Craig.