You think you have it all configured right, all common DKIM checks on the interwebs agree with you but still you receive replies prepended with [DKIM ERROR]. You dig and dig, find out that apparently only one major mail server vendor gives back those errors, but no real answer or solution.

Picked up the gauntlet (after having smelled the glove) and tried a mail to the mail admins with zero expectations of getting an answer back. But no, got a reply within a day! And guess what. No it’s not my DKIM configuration. It’s my private key. It’s too secure. No, for real. This major vendor errors out on DKIM keys bigger than 2048 bits:

DKIM: permfail key too large (d=autostatic.com s=dkim i=@autostatic.com)

So if you run into this and you’re using a 4096 bits DKIM key at least now you know a possible cause of this behaviour.