Spent the whole morning yesterday creating accounts, adding forwarding rules etc so that the users will not feel anything in the migration. The Dashboard was very slow yesterday, probably because of Murphy's Law! This morning, corrected our SPF records so that the new accounts also can send mail without spf softfail - needed to remove the mx records of gmail, which were anyway not required, since mail sent from gmail is anyway signed properly. So, now the SPF records have ip4: parts and the include: part as given in Google's Helpcenter.
For migrating other domains, will think about the options presented by Scott Hanselman, especially the part about transferring old mails via pop and the gXfer tool to one-click transfer all mails.