The overall issue sounds exactly like a battery with one or more failing/intermittent cells. If one cell is going and all the rest of the cells have a lot of charge, it's possible that the other cells can "carry the load" when the one cell checks out on you. However, if all cells are partly discharged, the other cells may be at a low enough voltage themselves that they cannot make up the difference, and the Battery Management System detects a dangerously low voltage and puts the battery in shutdown.
In general, when someone says "my battery dies at [insert number above 0% here]", my first instinct is "find a friend with a Note 4 and try their battery" or "drop 20 bucks on a new battery and see if that helps".
It's rare not to get a message "Yay!!! That worked!!!!" back.
I did that and it still didn't work!