I ran into this error for the second time so I though I would document it quick.  To use Multi Factor Authentication with Exchange on Office 365, the use of a specific PowerShell Module is required.  This can be found in the Exchange Online portal under Hybrid.  After downloading and running, the error message “Cannot Start Application” and “Application cannot be started.  Contact the application vendor”.

In details, you may see the line:

+ Deployment and application do not have matching security zones.

This is a common error with a simple solutions.  Be sure to log in and run the Exchange PowerShell MFA module form Internet Explorer (Edge may work too, not tested).