How to generate separate autoreply warning from postfix to senders not using DKIM?

Antispam/phish efforts with DKIM and SPF are weak if they're not widely enforced. I can't turn on strict no-DKIM rejection or emails will be lost, but there should be some penalty for domains not in compliance. Even medium sized recognizeable domains/hosting companies lack DKIM which is troubling.

How can I build a separate autoreply to any sender that does not employ DKIM (with some decay time before a second warning is sent for frequent senders). This would be in effect for all users of the system when receiving mail.

(I could perhaps do this via my MUA to process headers in reply and generate a warning, but this would be only for personal messages I reply to manually, not for my entire domain of users.)

Please do not do this. Despite it would be nice if everyone signed their email with DKIM, this is not a good path to achieve it.

Most of the automatic responses would go to the users that are not maintaining the mail system and, thus, unable to do anything to the issue. As a result, they could either get irritated or ask for your help on how to configure their email (client) with DKIM. A question you would not be able to answer.

Instead:

• Contact the email system administrators. Ask them why they have not deployed DKIM yet, and tell them about the advantages of DKIM and DMARC.
• If you prefix the the subject lines with [MISSING DKIM; POSSIBLY FORGED] on delivery, you won't be sending extra auto-replies. However, the sender will notice the Re: [MISSING...] on every actual reply.

The problem Esa Jokinen rightly points out about such messages not being seen by a suitable audience does not make the general idea entirely hopeless. Because you do not need to send this as new messages. Instead, leave such request in places that will (primarily) be seen by users & mail operators that do care and are able to do anything to the issue. The primary being:

SMTP extended status code & text

– the message that administrative folk glance at when trying to determine the nature of a problem with delivering mail to you. The response you already send in every case of spam filtering false positives. If you, like many operators, are guilty of custom, yet still unactionable messages, then start using that free real estate to leave a guide (or a pointer to a guide) how the situation could be mitigated. No new chatter, no change in accept/reject policy, just improving what is already communicated for some unavoidable share of incoming messages.

1. Bad: wasting of the ability to append free-form:

   550 rejected for failing to meet criteria which I wont reveal hahaha

2. Better: replace the existing text unconditionally with your link:

   550-5.7.1 Too similar to previously received junk, Please review
   550 5.7.1 https://support.example/mail/1337 for more information.
   

3. Fancy: If you are able to conditionally trigger this only on spam-rejects where nothing obvious (same domain, DMARC, known party) clarifies authorization, you can even include specific calls for action depending on what is most likely helpful to the sending side:

   550-5.7.1 Your system example.com does not appear authorized to
   550-5.7.1 send as example.org - Such messages could still be accepted
   550 5.7.1 if your mail provider configures DKIM for you.
   

If you have more than one spam filtering software - check all respective negative answers that you send with non-negligible frequency whether they truly use a more standardized & useful text. Just take care to not mismatch messages for transient and permanent rejections.

I think this should not be fully automated. Rejecting all non-signed mail is too strict, and changing subjects could be annoying too, and this time it will annoy your own users. Also consider the amount of stress for all parties when you finally apply this system, the day when your users suddenly won't be able to receive a lot of mail that was perfectly working yesterday, or when a lot of mail happen to have this garbage in the subject. I bet they will press you to revert the change, rather than trying to convince their peers to press their admins — this will be by far easiest apparent resolution for them.

You need to consider each domain on case by case basis and what can be automated is statistics. On reception you can collect the counts for each sender domain, how many mails it sent to you, and how many of them appear to be human-made and how many reverse traffic is seen (e.g. replies).

Then, you may select the domain which showed substantial traffic and build notices to their postmasters or domain owners in a semi-automated fashion, or, perhaps, apply the processing that is suggested in other answers only to those domains, or convince only a few users who talk with those domains a lot to add notifications in their MUAs. This will make the whole inception of the system less stressful, notices will be addressed more directly, while you won't bother notifying the operators of systems from which you had only seen only a stray messages without any response in their direction.

Update. Technically you can use something like this solution to create your notification emails. But again, I strongly advise you against sending such notifications to end users. They don't bother whether mails are DKIM signed or not. Email RFCs define postmaster@<domain> address for such notices.

If a part of email traffic from a domain is signed, and part is not, I think it is not worth writing to a postmaster at all. They prove they know what DKIM is because they are using it; the fact they don't use it for some mail could only mean they know what they are doing and there are reasons for doing so. If there is a DMARC policy, you should comply with it, because it is the manifestation of their view on the problem, and your notices and explanations won't do any good at all.