What's the best way to minimise e-mail downtime during a domain move to a new server?

OK, here’s the situation:

The aim of the game is to get “domain.com” from “Hosting provider A” to “Hosting provider B” while minimising the amount of e-mail downtime.

When the domain lands at Hosting Provider B, it will have its MX record pointed to Google Apps, and will be up and running fairly quickly.

My question is, would it be a good idea to add the domain to Google Apps before the move, or to leave the current setup (normal SMTP mailserver) intact? Will there ever be a point where the domain leaves the old host and is in limbo before it lands at the new one? How can I minimise the chance of lost mail for my client?

Thanks in advance!