You could try a master (factory) reset although my guess is that it's not a software issue, but hardware. As such, it's basically a process of elimination as it could be the wall charger, cable, battery or phone. Doesn't sound like it's the battery if it does the same thing with other batteries. So I'd try another cable or wall charger. Or check the ends of the existing cable, do they fit securely into the charger and phone? If they're loose, they may not be making enough contact to get the proper voltage and amperage through to fully charge the battery. If that's the case, try carefully crimping the ends just a bit with pliers to tighten up the connection.
Otherwise, you could always use an external multi-function battery charger (link below). This is what I use to keep my five batteries charged (two 1400mAh standard, two 1620mAh standard Rezound, one 2750mAh extended), rarely use the phone itself anymore.
Amazon.com: Seidio HTC ThunderBolt and myTouch 4G Multi-Function Battery Charger - Retail Packaging - Black: Cell Phones & Accessories
In the end, if it is the phone, it may be under warranty yet which you can contact Verizon for a replacement.