Hi @Cookies, I had a response. I was told the issue was that they made a configuration change for BFCM to alleviate the load on the servers that consequently affected stores with DKIM setup. This is now been sorted so in theory all your stores should be working again.
I noticed through our DMARC reporting that a small number of messages were still being signed by shopify.com. I contacted support again and it turns out these are account invitations, password resets, etc. These types of notifications are on a different infrastructure that hasn't been migrated to support custom DKIM yet. Support said that it will be migrated, but they couldn't provide a date. I tested this myself by sending test notifications and indeed it seems to be the case. I just thought I'd mention it on this thread in case anyone else wonders. So it's SPF authentication only for these messages for the time being, but given the small number, it's not a major issue, even with a reject DMARC policy.