In recent months I have two PRs come at me with the branch names being 'foo:bar'. Whenever I do a git fetch --all, that branch is nowhere to be found. How can I get this branch to be on my local machine?
That is an illegal branch name. You should look on github (or wherever these pull requests occurred) to see what happened here.
Note, however, that if you are managing pull requests correctly, it might be normal not to be able to find that branch because, if you're like me, you always delete that branch right after the merge anyway.