Ebenso wie die SSH HostKeys, müssen die SSL Zertifikate erneuert werden. Dieses mal habe ich jedoch nicht unsere eigenes (untrusted) Root-Zertifikat (CA) genutzt, sondern CAcert.org.
Deren Root-Zertifikat ist zwar (noch) nicht in allen Browsern eingebunden, sollte dies aber langfristig werden. In der Zwischenzeit kann man das Root-Zertifikat manuell in seinen Browser importieren. Danach sollte http://webmail.mkce.de und http://service.mkce.de keine Zertifikats-Fehler mehr anzeigen.