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. The easiest way to re-sync is to push the exact same branch name up to your VCS provider and run the deletion again to re-trigger the event.
Please Note: 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 it from the VCS provider to assure it will stay deleted.
Additional Articles: How can I delete a branch?