@jrevillini thank you, I didn’t see that message, but it looks like we’ve solved the issue (and seems to be staying fixed so far).
The solution was to move to a different hosting provider.
Everything pointed to the fact that it was a hosting issue and not our installation. The hosting company kept telling us to de-activate plugins, which we had done. Eventually, I thought to create a fresh installation on a sub-domain and it immediately had the same problem.
I also was able to request the hosting company to create a new SSL which didn’t work, and asked them to thoroughly check out VPS setup (caching etc.) but said there were no issues.
I transferred it to a new host and everything worked fine. And while that process was in place, I also thought to upload a clone to Updraft Clone and that also worked correctly.
Ultimately, there are still huge gaps in my knowledge, but in our case all signs point to the hosting company. I would recommend anyone having issues to use something like Updraft to clone their site for testing, and try moving to a new hosting. We chose WPMUDev because it looked easy (and it was) to move the site ourselves. I used their help chat to answer a few quick questions but otherwise it was quick and painless and extremely automated. I’ll post again if anything changes but hopefully this helps someone else fix their issues.