I've been keeping an eye on the discussion and need to reply to this.
Logy is 100% correct - physical (chemical) battery memory effect was eradicated with the NiCd (Nickel Cadmium) battery - a rechargeable technology that still has a place in photography where the particular discharge characteristics suit high speed flash, but that's about it : otherwise it's a cranky, crappy, dirty way to make a cell battery.
I also agree with Logy (and said earlier, although possibly on one of the posts Apple helpfully deleted) that I'm pretty sure there is more than one problem being rolled up here.
There's plenty of empirical evidence to suggest a software issue, which would see a short term 'fix' from battery replacement just as they do from what used to be called 'conditioning' back in NiCd days - but not for quite the same reason. In the case of NiCd, this busts the memory of the cellpack, in the the conjectured case here, it corrects a firmware counter issue. The important thing is that rechargeable technology has been chasing a holy grail of stable output voltage right up to empty - and Lithium Polymer like in the current iPhones pretty much achieves this goal. This is great as it means you don't need to make a battery bigger than it needs to be to account for a chunk that holds charge still, but discharges at too low a voltage to be useful in the application (think dimming flashlights etc) but also means that traditional battery meters which track cellpack voltage are not helpful. Apple are keeping very quiet about this, but we think their current firmwares are essentially counting units of charge going in and estimating likely use by some form of profile on the way out - the effect of which if you get these counters out of sync pretty much replicates the memory effect in software. If you have the software issue, then the conditioning deep discharges then full charge process is likely to get you running again for a few weeks.
There is a useful life on any rechargeable battery in terms of charge cycles, however. Apple quote about 1000 charges for the iPhone, and without very hard sums this should show that daily charging, which is what most people do, should give you around three years - at which point no iPhone 5 should yet have a problem but 4's and 4S's may. And this is where the second critical point is: if these '1000 cycle batteries' are not posting their forecast three year service life, are they fit for purpose? In the US it only really matters from a soft 'goodwill' point of view as Apple's one year warranty stands up unless you bought AppleCare. In the EU it's less clear cut though, and if there are a bunch of under specified or badly manufactured batteries out there, Apple could be liable to make good every handset sold going back two years - which is going to hurt the bottom line - although Apple and your Network will both try to tell you that the othe is the Vendor for the purposes of EU Law and you may need to be harder headed about your dealings than you should need to be.
The point is that as Apple are keeping quiet on this and the big Tech news outlets are ignoring the story still, we only have conjecture at this point and empirical evidence. It would be interesting if everyone here got their battery replaced and we reconvened in two months, but based on the number of people who experienced the issue first with nearly new hardware after a particular firmware update, I'd be surprised if wholesale battery replacement is the answer.
