Lacking your tie and other details it's hard to say, but at a guess, are you checking the DBM file via strings or some such? You may be seeing deleted records.

Write a short script that checks the valid keys in the file, or just add this debugging line after the delete:

print "Users = @{[keys %who]}\n";
[download]