Return 410 Gone when deletion fails

[jwreagor]

Currently we return 404 not found but we need to make sure clients understand that the request failed gracefully as the record was already deleted/archived.