Cleaning up orphan uploads should work for both local and S3 storages.
The only difference between the local and S3 storages is that the cleanup of the tombstone is automatically handled by S3 via a policy.
@Vikas_Dangi have you enabled the clean_up_uploads site setting? Are you sure that image isn’t used somewhere else (avatar, user profile, category image, etc…)?