Turns out mailman was set to deliver mail to an smtpd without milter support enabled so opendkim didn't run and didn't sign any outgoing mails. I've fixed that now so all mails from senders with a DMARC policy should be changed to the list address as the From header and they should be correctly signed by our key.
I've also noticed that some DKIM verification software (the thunderbird plugin) stores keys and does not update it's cache. Since the initial key was broken due to nameserver/webui problems, I've set up a new selector for each affected key. Sorry for bloating the zone file, but I think we should keep the old keys in there so that mails with the old selector can still be verified.
If anyone notices any more broken DKIM sigs or other weirdness please tell me.