So, der Umzug hat nun geklappt, vielen Dank!
Beim Zuordnen der Domain zum Webhosting wurden mir meine ganzen DNS-Einträge verstellt. Das habe ich leider nicht gleich bemerkt (weil man die DNS-Seite komplett neuladen muss, um die Änderungen zu sehen) und daher ein paar Probleme gehabt, die Einstellungen wieder zu korrigieren. Das dei TTL noch nicht auf 300 runtergesetzt war, hat auch nicht geholfen...
Nachdem die neuen Mailkonten dann eingerichtet waren, habe ich die Passwörter der alten Konten dann zurückgesetzt (damit ich sie kenne, root zu sein hat halt seine Vorteile) und mit imapsync rübergezogen. Danke Virinum für die Links! Mit ein wenig Einarbeitung hat das wunderbar geklappt! Die Performance war mäßig (ca 3 Mails / Sekunde), aber ich habe das Tool auch auf meinem Rechner zuhause laufen lassen. Wäre es auf meinem Mailserver gelaufen, welcher ja im selben Rechenzentrum wie der neue steht, wäre es sicherlich fixer gegangen.
Anschließend habe ich alle DNS-Einträge auf die Webhosting-Einstellungen umgestellt und hoffe nun auf einen reibungslosen Betrieb.