The fact that refs/remotes/origin/my_remote_branch exists in your local repository does not imply refs/heads/my_remote_branch exists in the origin remote repository.
Do git fetch -p origin to make refs/remotes/origin/my_remote_branch go away if it’s already deleted in origin. The -p option tells fetch to delete any tracking branches that no longer exist in the corresponding remotes; by default they are kept around.