Das erste was du wissen solltest, ist, dass DNS Einträge gecached werden, z.B. bei computerbase.de
Code:
#dig computerbase.de MX
...
;; ANSWER SECTION:
computerbase.de. 3600 IN MX 10 mail.computerbase.de.
...
;; ADDITIONAL SECTION:
mail.computerbase.de. 3600 IN A 87.230.75.4
mail.computerbase.de. 3600 IN AAAA 2a01:488:2000:201::b
In dem Beispiel sind es 3600 Sekunden oder 60 Minuten, wo mein System Mails an computerbase.de immer an mail.computerbase.de/87.230.75.4 schicken wird. Sollte ein Computerbase Admin den Einträg ändern, dann würde mein System es weiter machen. Bis maximal 60 Minuten vergangen sind. Erst danach würde mein System den aktualisierten DNS Eintrag mitbekommen.
Also solltest du nachschauen, wie lange die Caching Dauer für den MX Eintrag von deiner Domain MeinBespiel.de (

) ist und diese ggf. vor dem Umzug stark verkürzen (auf wenige Minuten). In der Regel sind es 86400 Sekunden oder ein Tag, wo ein Client einen DNS Eintrag cachen darf. Also kann es passieren, dass für einen Tag Mails in deiner alten Mailbox bei Hoster A landen, obwohl der DNS Eintrag bereits auf Hoster B zeigt.
Der zweite, wichtige Punkt, den man wissen sollte. Meistens sind die Mail-Server auch unter anderen DNS Namen bei den Hostern erreichbar. Also nicht nur über MeinBeispiel.de, sondern auch unter z.B. foo.HosterA.de und bar.HosterB.de. Damit kannst du unabhängig von deinem DNS Eintrag die Mail-Konten von A nach B migrieren, indem die Quelle foo.HosterA.de und das Ziel bar.HosterB.de ist.
Jetzt kommt es darauf an, was dein Hoster A und Hoster B anbieten. Gängig ist meiner Meinung das IMAP und POP3 angeboten werden. Es gibt diverse Tools, womit du z.B. über IMAP zwei Konten synchronisieren kannst. Damals habe ich für meinen Umzug imapsync unter Linux verwendet. Hat alles problemos geklappt.
Zusätzlich bieten einige Hoster einen Migrationsservice an, der das auch macht. Frag einfach mal, ob es so etwas gibt.