Space deleted but not reclaimed for re-use

Question

I'm using Nexus 5. In the following image, you can see that I have total space of 12.55GB. Apps in the dark green bar on the left taking up more than 1/3 of that with 4.93GB. The light gray "Available" which is nearly the same size is listed as 498MB -- that's much less.

If this were actually 498MB, that would be a tiny sliver, not nearly 1/3 of the storage space.

I've deleted a ton of pictures and apps from my device, basically bare-bones and otherwise not usable even to run the next OTA update. But no matter what I delete the space is never reclaimed on the device:

_{(Click image to enlarge)}

Why is this happening and how can I fix it?

My current theories:

1. I had an earlier rooted Android but lost the root in the first OTA. I was able to use SuperSU and whatnot then, so I know I was actually rooted.
2. On that update, I chose something listed as "Preserve root mode (experimental)" which did not work. Since that root loss, when I go into my recovery which I believe was Clockworkmod at the time, I don't seem to have a recovery either -- it says "no command".

So maybe the space I cannot recover is controlled by the root user and I can't delete it as a normal user?

Is it possible to restore my ability to use my disk space without wiping my data?

Answer 1

The update from 4 to 5 disabled my access to clockwork mod, but did not remove Clockwork or prevent it from doing whatever automatic recovery process I had set. So, that was building in the background until I deleted it.