You have a few options:

 

In addition to John Marx's suggestions (all of them perfectly viable) there is another option:

After setting up the email accounts in Smartermail you can use the Mailbox Migration Utility in Smartermail to import their email from their respective accounts on the old Mail Service (and in some cases import their Contacts, Calendars, Tasks & Notes). Once the migration is complete you can then change the MX Records in DNS (and probably SPF, any Host A Records used by your Smartermail Services, and SRV Records for CalDAV/CardDAV and Autodiscover if applicable). You shouldn't need to worry about normal DNS Propagation (which can sometimes take up to 72 hours) as Mail Servers normally should not use DNS Caching or Caching DNS Servers, meaning that once DNS is changed their old email accounts at their previous provider should not be receiving any emails after the change is made in DNS.