Meine Frage kann ich selbst beantworten - es hat einige Stunden gedauert, jetzt funktioniert es.
Die Lösung: Der DKIM öffentl. Schlüssel darf keinerlei Anführungszeichen (") enthalten, weder am Anfang/Ende, noch innerhalb des Schlüssels - alle entfernen und nicht durch Leerzeichen ersetzten.
Überprüfen kann man hier MXTOOLBOX