Will both ISP connections be active simultaneously for any period of time? If so, you can simply put a mail server on each connection, and manipulate which server is preferred via DNS MX records.
If not, things become more difficult. You can add a second DNS MX record (with a lower priority) for the mail server's new IP address will be sometime before the switch is made (I'd do it a week beforehand). Then when you switch, remove the old MX record and mail should immediately begin flowing to the new mail server.
