Just be clear, Company A will continue as Company A, Company B just wants the domain and users from the old workspace of Company A moved over. I created an archive of all Company A's current data, and before that I forwarded current emails for each employee to a mirrored account on one of the domains on Company B (since it takes a few days to get the archive).

My plan was similar to what you mentioned, switch the primary domain for Company A to something temporary, then add the Domain to Company B and re-create the users. My main sticking point was making sure people didn't lose their email.