A quick question:
Are you using the same chargers that you were using 2 years ago?
Here is a neat site that has a lot of articles on batteries, battery management and pros/cons vs. types:
http://batteryuniversity.com/learn/
Anecdotally, I have heard with specific types that there are different techniques you can do to increase a batteries capacity.
During the minibot effort in 2011, I heard many rumors of different tricks that would eek out slightly different performance curves. Slight changes to charging rates and voltages.
During my solarcar days, I remember hearing about a team doing controlled battery cycling using a specially designed oven to increase a batteries useable capacity. While controversial, I will say that particular team was able to run much longer in cloudy weather than all the other teams so I have to believe there was something to the effort they were doing.