2 Trusted Domains One Exchange Server

I'd use a POP3 connector. Here's how I'd do it:

1. Setup the accepted domain as an Internal relay in Exchange. This will allow Exchange to deliver messages to itself when the mailbox exists and forward them when it doesn't.

2. Migrate users in batches. Reset their POP3 passwords to whatever suits you (because they won't need them after the migration). Create an Exchange mailbox for these users then setup the POP3 connector on the server (you could set it up in Outlook but I believe this adds unnecessary complexity). Migrate users 1 department at a time or 1 manageable batch at a time. After setting up their Exchange profile, import their PST back into Exchange. You may take as long as you want to do this as impact is minimal.

3. When all users have been migrated, change the domain type to authoritative and move the MX records to point to your anti-spam solution (Your appliance, or better yet, a cloud solution). Wait 48 hours then remove the POP3 connectors.

I'd certainly suggest moving chunks of users out of their core hours (at night, as you say). Make sure the mailbox quotas on the new store are big enough!

As for how you load databases, I'd suggest you think about downtime to restore, say, 70gb of data vs. the tolerance of people in that database. You might group people in terms of the tier of service they want, or department, whatever works best for you. All I'd suggest is that whatever you do, you should structure it somehow and you should be consistent.