Okay so after trying literally everything I could imagine of, I think I finally fixed it, by using my own Gitlab Runner:
- I installed Docker Desktop on my laptop
- I followed the instructions on Gitlab about installing your own Gitlab Runner with Docker and registered my Gitlab Runner
- In the project settings I disabled using shared runners and set it so pipelines only run using my runner
- Tried to execute the pipeline and butler push didn't fail.
So it might be a temporary Gitlab issue? I don't know, I do still have to test it on a few more pipelines I have but seems promising