error: refs/heads/[branch name] does not point to a valid object!

Recently many of our old remote branches were deleted and our TC build started failing with errors like:

[VCS Root: GitHubCkoTech] [C:\TeamCity\buildAgent\work\Gateway_Development]: "C:\Program Files\Git\bin\git.exe" init
[17:08:51][VCS Root: GitHubCkoTech] [C:\TeamCity\buildAgent\work\Gateway_Development]: "C:\Program Files\Git\bin\git.exe" remote add origin git@github.com:xxx/xxx-api.git
[17:08:51][VCS Root: GitHubCkoTech] [C:\TeamCity\buildAgent\system\git\git-56AF2D58.git]: "C:\Program Files\Git\bin\git.exe" pack-refs --all
[17:08:51][VCS Root: GitHubCkoTech] [C:\TeamCity\buildAgent\work\Gateway_Development]: "C:\Program Files\Git\bin\git.exe" config core.sparseCheckout false
[17:08:51][VCS Root: GitHubCkoTech] [C:\TeamCity\buildAgent\work\Gateway_Development]: "C:\Program Files\Git\bin\git.exe" show-ref
[17:08:51][VCS Root: GitHubCkoTech] error: refs/heads/task/747-autoaction-config-transform does not point to a valid object!
[17:08:51][VCS Root: GitHubCkoTech] error: refs/pull/720/head does not point to a valid object!

I've tried setting "clean all files in the checkout directory before the build" but the issue remains. When I run the above commands directly on our TC server via Git Bash I do not get any errors.