I ultimately figured it out.
Apparently just allowing all private repositories (even for organisations) wasn’t enough, I had to go to each project page:
https://circleci.com/gh/[ORG]/[PROJECT]/edit#checkout
to fix checkout keys. Sometimes I had to re-add a project manually.
– Thibaut