To everyone out there facing this error, I solved it going through Apple Support. I sent them an email, and requested the ticket to be escalated to the engineering team - I linked this forum thread for additional information. They did that, and after 1 week, it was all working again. Apple did not say what the issue was, but I am sure there is no way we'd be able to fix it ourselves. No different configurations were tested, they just went radio silent and suddenly it was working.