The max-depth parameter only affects how many levels of subdirectories are printed. It won't affect the numbers for the higher levels. And besides, in your most recent invocation you didn't use that option, and that's equivalent to a max-depth of infinity.
I don't see any mention of you having run fsck on the file system. File system corruption is probably not the cause, but that possibility needs to be eliminated first. Create a /forcefsck file by running
and then reboot.
Assuming that the fsck doesn't find the problem, the next thing I'd suspect is data hidden under an active mount point, such as /dev, /sys, or /proc. You can find (and correct) that by bind-mounting the root file system to a temporary mount point and then looking under that mount point.
mount --bind / /mnt/tmproot
du --max-depth=1 /mnt/tmproot
Let's take a look at that result. Any directories that are active mount points at the base of the root file system should show up as empty directories (size 4K) in that list.