Been suffering through the warnings, too, and could not figure out the problem until today. For me, it turned out that Audible audio book files downloaded were in internal memory, but not showing up under any tracked category (not audio files, not pictures, not apps, etc.). I tried several apps designed to move/track/clear clutter and none of the ones I used found these files.
Even though the Audible app and most of the files attributed to the app were on my SD card, the audio books themselves were basically hiding on my phone.
Even if you don't have Audible, there may be another app that downloads/uses proprietary file types that hide on your phone. In my case this was almost 5gb of data!