Bei den beiden DKIM-Records key1/2._domainkey gehört beim Ziel auch jeweils ein Punkt ans Ende. Also key1._domainkey.webhosting.systems. und key2._domainkey.webhosting.systems.
Das war mir jetzt alles viel zu viel aufwand mit Hetz*ner!
Habe die Domains jetzt einfach zu Netcup umgezogen.