The phone has two batteries, one that you know about and the other that keeps the date and time correct when you take out the battery. If a phone is not used for a long time then this battery can become flat and you lose the time and date and any volatile information the phone has not got stored to memory.
If you have charged your phone and use it all of the time then what you might have is a faulty internal battery. I'm sure on phones these days that they are small and not easily replaceable so it might mean a replacement phone or a new system board.
Computers have this system and have what is called a bios battery, these on pc's (and laptops) resemble a watch battery and I had one go on my laptop. It too forgot the time and date when turned off.