I don't think this is necessarily an error.  The caller asked us to remove it.  Its gone.  If they really demand that we error out on this, maybe we have an optional flag that they should set:

  setFailDeleteIfNotExisting()

Or we should expose a Result type to the caller that they can examine, with two different results:

  DELETED
  DID_NOT_EXIST

Most callers are just happy that the thing they asked to remove is in fact removed, and don't care how that happened.