I would think if you have all new mail delivered to the new Domain B Exchange Server at a cut-off point, and have users log into the new Domain to get their mail, promising them that within 'x' time, their old mail will show up...
Then you begin the export and reimport of their mail on your schedule (maybe with VIPs first on the list)