How can I switch ISP’s with minimal downtime/switchtime?

Currently running on a cable ISP with two static IP’s sNAT’d to inside servers. We will need to switch our A/MX records to the new IP’s (on a T1). My thoughts were using a router that supports two internet connections and just setup the SNAT on both connections to point through. Other thing I want to look out for is getting listed as spam when the mx record changes over (spf records will have to be updated “on the fly”). NOTE: we won’t be switching dns hosts.