I'm not getting the equivalent of recovered disk space when I only delete (clear) a song or two from my iPod. If I clear more than 20 songs, or so; then the extra space will show up

.
I've faithfully kept up with the software/firmware upgrades, and my iPod has been in a nearly full state for some time now. Is anyone else having similar problems?