Hoople - 4:26 am on Nov 26, 2011 (gmt 0)
I personally use a combination of MX record priority and the two site DNS setups others above describe.
I test all new mailboxes (on the new server) for functionality with predefined passwords and both mailboxes opened in their client. I then do the DNS flip for the website's A record. Once I see that working I raise the MX (Mail eXchanger) priority on the old site and drop it on the new site.
After a time the cached DNS attributes scattered around the 'net time out and mail flow to the old site drops to zero. I give it a bit more time and then drop the old site MX record.
Sorry if this seems more complicated - I'm a email guy by day doing web as a sideline.