If you buy in to the idea that the battery needs to be conditioned to fully utilize a full charge, the fact that you are always plugging it in when it's only at a 60%-70% charge may have conditioned the battery to not take in as much of a charge and, thus discharge more quickly. I'm not sure if there's any real science behind the theory, but I for one always try to let my battery run down as low as possible before charging and let it actually die before charging at least once a week. I'm not sure if there's a certain window of time when you first get the phone to condition the battery though or if you can do it now.
Conditioning batteries is a carry over from NiCad batteries.
Li-ion batteries don't need to be conditioned nor is it recommended.
What you may be running into is a the battery level not being calibrated. What I suggest doing is letting your phone go all the way dead and then charging it up to 100%. What I am guessing has happened is that your battery level was never calibrated correctly so it's giving an improper return on the remaining battery level.
EDIT: I just read your post. You need a new battery or phone. Talk to Verizon there is something wrong.