My battery was crazy for the last several days. I had 20% at 5 PM when my iPhone 4 gave me 50-60% at that time. More ridiculous I had turned almost every single app and notification, location OFF. iCloud off, I felt I was just with an internet browser alone.....
So, After reading many posts... I decided to try the last resort.
Reluctantly, I let the battery go to 8% and did a restore; restored as a new phone. Re-installed all the apps, accounts, etc.
Let charge and left plugged in overnight.
Today, I unplugged at 6 AM. Battery was much better. I used it regularly, even on 3G and at 7 PM I had 54%.
I did go to the apple store (because I had an appointment) and the guy checked my battery and said it was fine (I saw it). He also plugged his phone and even showed me his battery was lasting less than mine. He said if I keep having issues, they will replace it but I said I will give it a try, especially during the week.
Anyway, I would try this first. AND NO, this has nothing to do with the phone not fully charging; that is a completely different issue.
hope it helps.