If you over discharge a LiIon battery, and leave it in that state for a long time, then you can indeed damage the battery. Note that "over discharge" does not mean "0 volts". I believe taking it down below a certain point (but still above 0 volts) is considered an over discharge. LiIon batteries that are in this over discharge state develop internal changes that destroy the battery. Sometimes a sophisticated LiIon charger can rescue batteries from this over discharged state. I highly doubt that the charging circuit in the Kindle is one of these sophisticated ones. Probably, a new battery will be required.
You said you've already bought two new batteries, but they acted similarly. Where did you buy these batteries? Was it from a reputable dealer? If they seemed like "such a deal because they were so cheap", well, you probably bought two batteries that were used and already destroyed themselves.
I did find some internet articles that mention LiIon over discharge problems for you to read:
https://batteryuniversity.com/learn/...oltage_cut_off
https://electronics.stackexchange.co...main-in-this-s