The technology in Wall*E is so bonkers I would happily say it's because of magic advances in battery technology. But that's not satisfying, and not even internally consistent, so let's polish this turd and make it work!
Wall*E is fantasy, an analogy for the unsustainability of modern society. Wall*E, as a hero in the story, is supposed to represent frugality. He recycles. He's solar powered. He's making tiny contributions to cleaning up the mess that turn into huge results. The analogy doesn't hold up when you realize he's just shoving the problem around, then again, he was designed by the people who made the problem in the first place.
You've spotted a major problem with the science of the film, it takes place 700 years after the Earth was abandoned, and the disposable technology Wall*E relies upon will naturally degrade. Plastic will break down in sunlight and become brittle (no spork). The tape in his precious VHS of "Hello, Dolly!" would have crumbled. And, yes, most batteries would be running at a small fraction of their original capability even if they've been just sitting around.
Wall*E's batteries are the least of the scientific problems with Wall*E. Consider The Axiom. Having survived for 700 years in space in leisure, the Axiom would appear to be the epitome of sustainability. Why didn't they use that sort of amazing recycling technology on Earth? (Remember, any tech they had on the Axiom they had on Earth.) The Axiom dumps their trash into space, how do they sustain that for 700 years? The Axiom is an analogy for humanity having knowing how to save the Earth, but finding it easier/cheaper to trash somewhere else, just like we do now. Great analogy, bad science.
The world of 2100 (when the Axiom was launched) appears to have made some huge advances in AI, space flight and (ironically) recycling. The Axiom has hyperdrive, robots smart enough to keep everything running for 700 years with minimum human intervention, and has sustained a large human population. With all those robots running around, it's fair to say they've got good batteries. The energy density of batteries has been getting better at a rapid pace for decades now. What about their lifespan?
The primary way current batteries die is by the charging cycle. After four years and 1000 cycles, my laptop battery is down to 60% it's design capacity. With special equipment this can be reversed, but only so much, and certain types of batteries respond better than others (do not believe what you read on the Internet about battery reconditioning at home).
But batteries also degrade on the shelf. The shelf life of a rechargeable battery is measured in time and temperature. Different types of batteries have different optimal storage requirements, but the time scale is a few years and Wall*E takes place 700 years after the Earth was abandoned. Could Buy N Large have built a battery to last 700 years? Absolutely! But would they?
Buy N Large has created a disposable society. Why build a battery that lasts 700 years when you can just throw it out and make a new one?! And who wants last year's battery when next year's batteries will be better?! This is obvious for their consumer products, but the robots are different.
Like many predatory corporations, Buy N Large is happy to sell you a non-sustainable lifestyle so you'll keep buying. Cheap in the short-term, expensive in the long. But Buy N Large itself would be ruthlessly efficient taking short term loses to ensure long term profits. The durable, sustainable, smart, self-repairing robots of Wall*E are an investment in the future of low cost labor. Might Buy N Large develop long shelf life batteries for these robots? It's plausible if they thought it would save money in the long run. Would they last 700 years? Probably not... but the law of averages says some of them will, and there's a lot of dead robots to average it all out.
The fact that so much infrastructure is still standing (buildings, ships, highways...) after 700 years is a testament to how well things could be constructed in 2100. The lack of life on Earth to pull everything apart would help preserve things, but there is still the corrosive effect of water and effect of ice expanding in cracks.
Other possibilities include...
The rate of capacity loss is not linear and diminishes as the battery gets older. Wall*E could have originally been designed to go for weeks without charging. Now he can barely manage a day on what he can scavenge. He could even be using batteries from larger robots with larger capacities (but the same output).
We know the humans abandoned the cleanup effort after just a few years, but the robots kept at it. We see Wall*E as the last robot, but that's only in his particular area. There could be other robots still functioning. There could be an automated parts factory somewhere. Even if Wall*E is the last functioning robot, he doesn't have to have been that way for 700 years, that could have happened the day before the movie started.