Ok, I just had the same issue as the original poster and I finally worked out what happened and how to avoid it.
It's basically what Elbega said. When you save a game then turn off your DS, that save is retained in the SRAM as you all know. For some reason, some DS Linkers have a tendancy to either lose or corrupt this save after a period of time. If this happens, when you turn it on and boot it up, it's backing up an empty/corrupt save game which is why you have to start from the beginning of your game again. Just turning it on again straight after you turn it off to back up the save likely would work - if the DS Linker didn't insist to backup that SRAM on every damn bootup (preferred behaviour would be to only back up once). Which means when you turn it on later the SRAM is likely to have died by then, and it then overwrites your good save backup with the bad one.
The way to avoid: just turn your DS straight back on again after you turn it off (after playing a game) and let it back up your save. Then what you must do is start (boot) either a placeholder game that you don't intend to play (or one that has no saving whatsoever) or some sort of homebrew application (I use DSPad or DSKey that comes with the OS) . After that you can turn off your DS and leave it off.
Alternatively you can set FORCEBACKUP=0, then turn on your DS as soon as you turn it off just like above, then select the game you were just playing and press Start. This way the save won't ever overwrite the previous one unless you tell it to - just be sure you don't press Start again later on.
This is quite an annoying issue, and be the problem battery or not, I think we should at least contact the people behind the OS to see if they can change some of the saving behaviour. My EZ4 uses a battery with SRAM, and has not had one problem since I got it a year ago - save games can stay in the SRAM perfectly fine for days or weeks.
What I would suggest people do is use the SRAM/battery testing application at
http://www.dslinker.com