ALL shows all content on the device and on Kindle Cloud.
DOWNLOADED only shows local content on the device.
If deleting the problematic book directly from Kindle in ALL doesn't work, OP could go to
https://www.amazon.com/myk to delete it directly from the Kindle Cloud (might be under Docs instead of Books).
That said, it's possible that the flash storage on the Kindle is starting to go.