When I do git fetch origin and origin has a deleted branch, it doesn't seem to update it in my repository. When I do git branch -r it still shows origin/DELETED_BRANCH.

How can I fix this?

You need to do the following

git fetch -p

The -p or --prune argument will update the local database of remote branches.