Hi David / Jaron
One thought - typically dmarc gets dkim validation from a separate milter dmarc.
And many folks still run opendkim which is unmaintained. Versions prior to 2.11.0.Beta2 (which arch kindly offers) are definitely broken. I don't even trust that one.
Jaron do you run opendkim by chance?
dkimpy-milter seems to work much better than opendkim, though of course you cannot help what other people's servers run.
I see your dkim is relaxed/relaxed which should help keep your mail flowing as well.
Just a thought.