You really need to get your hands on some sample messages to solve the problem. Hopefully you can collect this from one of the recipients that was not blocked. Once you have examples, here are some possibilities to investigate:
Are the Signatures Missing Completely?
There was a bug which has been reported frequently in this post, where DKIM credentials are lost and as a result messages have no signature. The solution is to recreate the DKIM keys for each domain, which of course is frustrating in direct proportion to the number of domains under your control. We have been assured that this is a one-time problem, and that has been my experience. When I first configured SM to apply signatures, the administrator chose the DKIM scope identifier. In more recent releases, SM chooses the scope identifier. I think the bug is related to this transition. Build 8223 and 8251 seem close enough that I would think you would have encountered this problem already, or that it had been fixed so it will not happen to anyone anymore.
Are the Signatures Unverifiable?
DKIM applies to the headers that are specified in the signature's header list. If the originating system does not supply a message-id, but includes message-id in the header field list, then the signature will be invalidated if SM adds a message-id header.
If SM adds the message-id header and adds a signature (for the same domain), then any non-verifiable signature should be be ignored and the verified signature should be accepted (if the recipient implementation is complaint, which seems likely.)
If SM applies a Message-ID header and adds a signature, it might not be including the added field in the signature calculation, which would be a bug.
If your source system supplies the message-id, then SM should not be adding anything and no signature problems should be expected. SM seemed to think that this was the norm, and this most recent patch was to handle the exceptions.
You should be able to evade message-id problems by ensuring that message-id is not in the header list of your signatures.
Finally, missing signatures should only be a problem if your domain is publishing DMARC with p=reject. You could consider changing to p=none before your next test.