If you have full control of your DNS zones (e.g. can reload zones on demand), you might want to shorten the TTLs to 600 shortly before the move, say about a day in advance. After the move, increase the TTLs back to the previous value, usually 86400.
NOTE: This temporary change does mean that your DNS provider will temporarily receive more DNS queries. But that's OK. After all, that is the idea. By shortening the TTLs, you're telling users (and caching servers) that your domain may change soon. The additional traffic is usually insignificant because DNS queries are very short. I've moved relatively large sites (tens of millions of hits per day), and it has worked well for me.
If you're not familiar with DNS zone files, the two relevant TTL values are the "$TTL" line at the top of the file and the last number in the SOA section (sometimes called the "minimum"). Remember that each time you update your zone file, you must increase the serial number (first number in the SOA section).
If you feel that a day or so of downtime is OK, this is overkill. However, you may want to implement this anyway to ensure continuous (or at least very close to continuous) email service.