I had the same thoughts and checked the paper[0]. They address it under 3.3 Delete
>Deletion does not have to clean the entry after deleting an item. It also avoids the “false deletion”....
>Deletion does not have to clean the entry after deleting an item. It also avoids the “false deletion”....
An item's position in the table is derived from two things: a fingerprint (a constant-sized hash) and second hash (ranging over the table). Nothing prevents two or more items from colliding on both hashes and therefore being indistinguishable from each other.
If the number of items in such a collision exceeds twice the fixed bucket size then deletion may result in false negatives.
In most practical applications there will be no useful way to bound the number of collisions. The paper shows results with bucket sizes of 4 and 8, but I don't know what the real-world probabilities of breaching these limits would be.