After upgrading to the newest version of TeamCity and enabling native Git (support introduced in 2022.04), roughly half of our builds just immediately failed with the following error.

Failed to collect changes, error: git -c core.askpass=C:\TeamCity\temp\pass8002850170451139133.bat -c credential.helper= ls-remote origin command failed.
exit code: 128
stderr: fatal: 'origin' does not appear to be a git repository
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists., VCS root: "GitHub" {instance id=1850, parent internal id=118, parent id=GitHub, description: "<supersecret>"}

No changes to VCS roots were made, and even projects sharing VCS roots had different results; some worked, some didn't. Didn't really make any sense.

After looking for solutions for quite a while, I found that simply clearing the git cache in TeamCity was the trick. You'll find it under Administration-Diagnostics-Caches,  then just hit Reset by git.