We first had no idea what was going on. GCP support just told us "it seems you deleted your CC". Eventually, we figured out what happened.
Set up a new payment profile and started migrating our GCP projects to it. Eventually had to create multiple of them, because there is an arbitrary quota of how many projects you can have per payment profile (~4), and support told us it would take days to increase it.
Fortunately, all our data was still there. However, support had initially told us that it's "all gone".