Google-apps – How to export Outlook.com emails to Google Apps

I followed the steps below and this fixed the problem.

1. Sign in to the administrator console provided by your domain provider.

2. Locate the page from which you can update the DNS records.
   
   If you want to authenticate mail sent from a subdomain whose DNS records you can't update, you can add the TXT record to the parent domain. Click here for details.

3. Create a TXT record with the name and value from the Google Apps control panel.
   
   The information you need in order to create the TXT record appears in the text box on the Authenticate email page in the Google Apps control panel.
   
   
   
   Different domain registrars use different names for the fields associated with a TXT record. For example, GoDaddy has fields named TXT Name and TXT Value, while Name.com calls the same fields Record Host and Record Answer. Regardless of which provider you use, enter the text under DNS Host name (TXT record name) into the first field and the text under TXT record value into the second field.
   
   If your domain host is EasyDNS, add a period and your domain name to the end of the DNS Host name (TXT record name) value. The value you enter should have the form google._domainkey.your_domain.com, where your_domain.com is the name of your domain.
   
   For detailed instructions about creating TXT records, including specific instructions for popular domain hosts, see Create a TXT record. See this article for limitations with some domain hosts.

4. Save your changes.

Source.

The issue was the iPhone defaults to "sync last 3 days" in the settings. And because the migration started from "oldest" to "newest", some of the newer email that would have fallen in that time windows didn't exist (migrating took 2 full days)