Macbook Pro sudden shut down when on battery power
I have a 17" Macbook Pro mid 2009, 2.8GH with all original components and very good battery (only 350 cycles). I've recently noticed that the computer shuts completely down randomly, only when on battery power, works completely fine with charger. My macbook is in pristine condition and never been abused as it was used as a secondary desktop computer always plugged in, except every now and then I would completely discharge and recharge a full cycle.It shuts down mostly when battery is below 65%. The screen just go black and the all computer shuts altogether with a clicking sound. Do you know what it could be? I took the cover off to take a look at it and cleaned the vents, disconnected and reconnected the battery, all seems in really good shape inside. I did an SMC reset but didn't help. I even try to connect a brand new battery (just in case) but that didn't help too.
Anyone as a clue?
Thanks
MacBook Pro 17″, OS X 10.11