Ok, the original question asked for methods, not the root cause, which I'll give here.
But I don't like to leave the question unanswered. No disrespect to all fine suggestions that I've received. Thanks to everyone who've contributed to us finally being able to resolve this.
It all went a lot better after we realized that the issue was related to setting the time in october, rather than some obscure bug going into december.
The culprit was a bug in the INT to BCD encoding of the month value, where the original author mistakenly added 1 to the BCD encoded value, rather to the INT value before encoding it; resulting in october being sent to the RTC as 0x0A, rather than 0x10.
The clock happily steps from 0x0A to 0x0B when going into november, and the BCD to INT routine wasn't too picky about getting invalid BCD values. It still got the 0x0B right (BCD 0x0B to INT = 0x0B, however 0x0B is not a valid BCD value...).
I have not yet confirmed how we ended up in april, that is still on my TODO for this.
I am rather confident however that I am finally on to the real root cause of this issue.
@Kellenjb: and you were right, too: it was a firmware bug :)
Update
OK, I have now confirmed that when the DS1305 goes from the invalid 0x0A month value (October) it ends up with 0x0B for November. With a naive implementation of BCD to INT (one that doesn't check the BCD input for validity), BCD 0x0B == INT 0x0B, so it still works.
It is when the DS1305 is to increment 0x0B (in seeing 0x0A go to 0x0B, one could expect 0x0C, but no) it ends up with 0x04 when going into December.
Mystery solved.
There are few factors:
1) As it was mentioned - battery self-discharge. I've checked few datasheets and it's 1-2%/year at 20-23C. If your device will stay in hot place (70C under direct sunlight for example) - it will self-discharge much much faster. Also, if device will be frozen accidentally - battery might be damaged and loose capacity.
2) PCB leakage - can reach hundreds of nA in case of severe surface contamination in wet conditions. If you manufacture PCB in good place, clean & completely dry it, and then cover it all (including chips) with some protective layer (polyurhetane or something) you can virtually guarantee no leakage through device life.
So, if leakage won't be an issue, no extreme thermal conditions - device will likely work for about 20-30 years.
Best Answer
A diode steering type setup is common. As long as the supply voltage is slightly higher than the battery voltage the diode will stay reverse biased. If the supply voltage drops out then the battery will take over automatically. Using a Schottky type diode can help reduce the forward voltage drop. Also, the device would have to detect the missing power supply and go into a hibernation type mode not to kill the battery too fast.
simulate this circuit – Schematic created using CircuitLab