Laptop randomly restarts thinking the battery is dead

I have a late 2013 15" MBP that just sleeps all of a sudden and then restarts. It has been happening for over a year now and for a while I have just dealt with it. It appears the laptop thinks that the battery is at 0% and thus goes to sleep. This is because a couple times this has happened, the icon to plug in the computer appeared. Most often it happens when not charging, and tends to happen consistently around 85% and 62% battery (but is otherwise unpredictable). Every once in a while it sleeps when charging as well.

The laptop passes all of Apple's tests, and as expected they have told me all they can do is send it in for parts replacement (basically, new logic board). Multiple authorized repair shops have told me a battery replacement could be worth a shot. Feeling confident this was the most likely (and cost-effective) fix, I did a battery replacement myself. All went well and the last step was to calibrate the battery. First discharge of the new battery, a few restarts happened. I then charged to full + 2 hours, and used the laptop for some time to discharge it again. During this time, no restarts! To finish the calibration, I had to bring it to 0% and then wait 5 hours to fully deplete the battery. Charged it to 100% (at this point calibration should be complete), used it without charging until ~%48 (no sleep at 85% or 62%; I am confident it was fixed during this time). I then put it away, used it later in the day and the restarts were back.

Figuring it has something to do with cycling the battery to properly recognize when the battery is at 0%, I discharged it again, charged to full + 2 hours. I am now using it, but am experiencing restarts still. I plan to continue cycling it (requiring me to fight through the restarts...not good for my workflow...). Whenever done with my work I will fully shutdown the laptop. I hope this usage will identify more of a pattern, but otherwise I am pretty stuck on this issue. It has been getting worse (more frequent restarts) over the past few months, and could really use some advice.

Other repair shops and I have also tried resetting SMC and PRAM multiple times to no avail. It is also probably safe to assume the battery replacement made no difference, and the (partial) battery calibration had more of an effect. Other people have reported similar problems, but most are not quite the same behavior that I am experiencing.

CoconutBattery: