Recently we moved a client from MDaemon to Exchange Online. Because the individual user's setups were complex affairs, with lots of users attached and lots of PSTs, we wanted to move them individually, rather than trying to do it all in one hit.
The approach suggested by Microsoft is to forward mail to the .onmicrosoft.com accounts as they are created. However, this doesn't handle return mail from the cloud to the onpremise server.
The way I solved it was this:
1. Create the organisation account customer.onmicrosoft.com in the Exchange cloud, specify it as shared, add customer.com.
2. Set up the onpremise mail server with an alias domain of smtp.customer.com. As there was already an A record for this there was no need to change any DNS.
3. Create all accounts in the cloud, specifying they forward to email@example.com. Set customer.com as default sending address.
4. As accounts are moved to the cloud, set a forward from their account on the onpremise server to firstname.lastname@example.org. Delete the forward from the exchange cloud account.
In this way we could move individual mailboxes without compromising their ability to email everyone else in the organisation. Once the migration is complete, we can change the MX records to point to the cloud and remove the onpremise server.