I did not save any certificates manually, I just set up MfE settings through the wizard and the initial sync was successful. (Actually I was amazed at that point of time how easy it was to set up.)

However, after the initial sync, the phone has synced successfully only very occassionally (probably 1 in 100 attempts is successful or something like that). If set to automatic sync, the error message is displayed repeatedly on phone display, which makes phone basically useless so I have now set MfE sync to manual.

After reading the forums, the reason could be also that our Exchange server enforces password on the device.

Is it possible to say from the error message that I am getting ("Error: Either Exchange server requires secure connection or account is disabled.") if this is related to the password enforcement or is it some sort of certificate issue?