Microsoft has recently (11/17) released an update to the CRM Online Email Router. This update adds support for connectivity between CRM Online and Exchange Online. The CRM Online Email Router Installation Guide has also been update to reflect these changes.
Microsoft Exchange Online support
With the November 2009 Service Update, the Email Router supports Microsoft Exchange Online. With this support, the Email Router can be configured to connect to Exchange Online mailboxes to process incoming and outgoing Email messages by using Exchange Web Services (EWS).
Microsoft Support created a scenario’s doc titled "Microsoft Dynamics CRM: How to configure the On-premise and Online E-mail Router in different deployment scenarios" to provide additional guidance.
I will be posting another blog with details on how to configure and a corresponding video. Keep checking back as I will update this post with links to each.