Most of the times you lose some emails in the propagation or forget to add that crucial email to the new host which means emails may bounce, etc.
That is when Google Apps come into play and make host transitions easy. To ensure that you don't lose any email sent to any of the emails of the domain you will need to create a Google Apps account (I use the Standard Edition but if you are creating one for a big company with lots of employees they might need the Business Edition) in advance of the move to the new host to ensure no email is lost.
Start by creating a Google Apps account and and then changing your current host's MX entries to Google Apps servers. Add ASPMX.L.GOOGLE.COM to the list of servers with a priority of 0. Increase the priority number of the existing servers so Google server is the only one with a 0 priority.
After changing your MX records, click I have completed these steps in your Google Apps control panel. This notifies Google to verify your MX records. The message Updating appears next to the Email icon on your control panel Dashboard, then changes to Active once your MX records are verified. At this point, you can receive mail in your Google Apps email account. You can access your email via the http://mail.google.com/a/domain.com default direct url or you can change the URL to make it simpler to remember to http://mail.domain.com. You can also chose to retrieve the emails via IMAP to your email client or smartphone.
Handling several emails or users
If you had several emails on the old host and would like to keep them separate you can do that by creating separate users in Google Apps. The Standard Edition allows for up to 50 users. Any new user will have access to their account separately and can login to their account by using the default URL described above.
If you had several emails but would prefer them to be delivered to one single account and then handle them via filters you can set up a catch-all under the Email Settings/Catch-all address. Once catch-all is enabled you can create filters in your inbox settings to handle any of the emails received under any other email than the primary email to the account.
Moving service to New Host
Once you have your new host account setup and have access to the new host's cPanel, proceed to go through the same steps to change the MX records to Google Apps. You won't need to verify your MX records with Google as this was already done through the old host.
Now that both hosts have the same MX records settings you can then change your domain DNS server to point to the new host.
During propagation the emails will be routed to Google Apps by both hosts which means that no matter what they will end up in your Google Apps inbox. Seamless transition without email pains.
