CircleCI automatically deletes branches when we receive a branch deletion event from your VCS provider (GitHub / Bitbucket). For various reasons, this may become out of sync.
Push the same branch name up to your VCS provider
Run the deletion one again to retrigger the deletion
The branch should now be deleted.
If you attempt to delete a branch while a job connected to that branch is still running, the branch will be re-created in CircleCI when the job is finished. Please allow all jobs running on a branch to finish before deleting them from the VCS provider to assure they will stay deleted.