I had the exact same problem and when the posted links failed I decided to do some digging of my own. The answer is actually very simple.
Open Mail security
Enter advanced menu (F5)
Under "Server" section:
On-demand database scan:
"Set" User Password
Click on "Assign"
SSL ON
Ignore server cert error ON
Below Client Certificate, click "select" and choose the active certificate in use on exchange. Check either in EAC or IIS Bindings if you aren't sure which to select.
After that you should be able to start a scan successfully.