How to test a delete operation?

Question to the community: How can you best test a delete operation?

For e.g. When you test the following API - DeleteObjectFoo("ABCD") - what should we test to verify that this function actual deleted "ABCD"? This API is just a placeholder for an API that deletes something. The question is that, in general, how do we verify that "something" was indeed deleted?

Should we simply test that "ABCD" is deleted from the database (or whatever the underlying storage is)? That is typically what is done. The question then becomes how do we catch a bug which not only deletes "ABCD" but also "XYZ"???

A colleague some time back had raised this issue since we ran into exactly this sort of a bug and found to our dismay that the existing tests were not catching this bug.

What do we change to test for a delete operation in general so that the testing becomes foolproof - or can it even be made foolproof?