Potential Issues
When it comes to mail flow, Microsoft would like email to flow directly from Exchange to Exchange Online and the reverse with no intermediary devices (unless it is an Exchange Edge Transport Server). This means that email should not be routed to a forwarding service, a hosted mail filtering service or an email appliance. In order to make this happen, Firewall ports need to be open, change requests made and security teams convinced of the needed changes. In order to make the change more palatable, we can lock down the Firewall to allow port 25 for any current connection limitations as well as Office 365 with the provided list that Microsoft has provided HERE. So that covers one potential issue – removing other intermediaries from the mail flow.
Next issue could be a rule in Exchange that stamps emails with an ‘External’ marker when an email arrives from a server other than an internal server. There are some work arounds for fixing this issue and one of the easiest is to create an exception for emails that are stamped with a certain header value that only comes from their Office 365 tenant. This header is called ‘X-OriginatorOrg’ and should be set to an internal Accepted Domain. Adding this to the rule should help exclude it from the stamp.
** TIP **
If you have a mix of Exchange 2010 and newer servers AND the Exchange 2010 servers are accepting Internet emails (and those from Office 365) make sure to edit the Transport Rule on an Exchange 2010 server otherwise the rule suddenly breaks. You will see a message like this (so be careful editing rules!):

Some other potential issues that you may have with routing emails is if you use an appliance, emails can get stuck in the appliance or is you using a hosting service, the same could occur. Secondly, if TLS or your certificates are not configured correctly (wrong certificate, wrong name, etc.) this could also potentially cause issues. In order to troubleshoot this, you may need to check Protocol Logs for your Receive Connectors to see how the server is answering and what certificate it is utilizing for TLS.
End Goal
And what is the end goal for all of these changes? We want to see this header in each and every message from our Office 365 tenant:
X-MS-Exchange-Organization-AuthAs: Internal
If we do not see that, emails from Office 365 are being marked as external which can cause issue with voting buttons, compliance and meeting rooms to name some potential issues. This makes this process important enough to hammer out with pilot users and can be a show stopper for some migrations.