This is how I believe it to work:
If you set up all your mail addresses before the change over, there shouldn't be any downtime. When they switch the name servers, all mail from that point on gets forwarded to the new mail servers. So if you don't set up the addresses before the switch over, you could have people sending mail that gets rejected.
Where you can lose mail is if it gets sent to the mail address before the name servers are switched, and the person doesn't check their mail before switching servers. It gets stuck on the old server, and I believe is inaccessible, although I could be entirely wrong. What I did with my company a few monhts ago to get around this was have everyone leave their computers on the night of the switch over. I then had them set their mail clients to check for new mail every minute. The switchover happened in the middle of the nite, and at the most they lost 1 minutes worth of mail.