This fix worked for me:
1. Delete Exchange account that is not working from "Mail, Contacts, and Calendars" in System Preferences;
2. Add new Exchange account using server settings;
3. If any "Certificate Verifications" pop up, click "Connect";
4. Wait for Mail, Calendars and Contacts to communicate with Exchange server - for me, I waited until I started seeing calendar events in the Notification Center;
5. Open Mail app;
6. Go to Preferences in Mail and navigate to Exchange account;
7. Uncheck "Use Autodiscover Service";
8. Fill in the External and Internal Server fields with your External Server information, e.g. "mail.yourserver.com";
9. On the Advanced Tab, check "Use SSL" for the External Server Path;
10. Click on "General" Tab, which then prompts you to save changes you made to the account;
11. Wait...BE PATIENT. It took a while for the Mac to communicate with our server, but I noticed after a period of time that the Mail Activity area was importing a lot of messages, i.e. inbox, sent, trash, other folders.
12. Unlike other attempts to install, I did not interrupt this process by clicking the inbox, or the sent folder, etc. Just let it work;
13. If any Certificate warnings pop up, click "Connect"
Again, this worked for me after no less than 30 failed attempts and alternative configurations.