I'm reasonably sure that the email router for CRM 2011 supported Exchange Online from the start (RTM). However, after you install the email router you should apply the latest update rollups (for an RTM installation, apply Update Rollup 6 and then 18) or
use Windows Update.
The error may be referring to the MAPI components that are needed for the Rule deployment wizard. Try installing the router without selecting the rule deployment wizard - that should work. Or you can install the MAPI components from this link
https://www.microsoft.com/en-us/download/details.aspx?id=1004 and then try selecting the email router service and the rule deployment wizard.