All of your questions are answered in tied hashed and deleting keys and their valeus (sic), a recent thread on this behavior of DBM files.

To summarize: It is an optimization that DBM files do not shrink when keys are deleted. Shuffling the bits around on disk every time a key is deleted would be too slow. Instead, the space is reused the next time a key is inserted. Read the aforementioned thread for more details.