The error message says: 'The remote certificate is invalid according to the validation procedure'.
This means that the certificate used by the Exchange Web Services HTTPS endpoint is not installed in the Trusted Root Certification Authorities store.
There are two registry-based certificate stores: per-user and per-computer.
The pre-defined Certificate Manager MMC console (stored in certmgr.msc) only displays the per-user certificate store.
To install the certificate into the per-computer Trusted Root CAs certificate store, you need to do the following:
1) Run mmc.exe
2) On the File menu, select Add/Remove Snap-in. option.
3) In the 'Available snap-ins' list, select Certificates, then click 'Add >'. A dialog box should appear.
4) On the 'Certificates snap-in' dialog box, select 'Computer account' option, then click 'Next >', then click Finish.
5) Click the 'OK' button.
6) 'Certificates (Local Computer)' node will appear in the console tree. Expand it, and navigate to 'Trusted Root Certification Authorities' node.
7) Expand the 'Trusted Root Certification Authorities' and go to 'Certificates'.
8) On the Action menu, select 'All Tasks', then select 'Import.'.
9) Click 'Next', then specify the certificate file (.CER) used by the Exchange Web Services computer for HTTPS communication.
10) Click 'Next', then 'Finish'.
How to obtain the .CER file to use on step 9:
1) Navigate to the Exchange.asmx page using Internet Explorer.
2) Click on the padlock icon next to the address bar, and choose 'View certificates' option.
3) A dialog with the certificate information should appear. On this dialog, navigate to the 'Details' page, then click 'Copy to File' button.
4) A dialog titled 'Certificate Export Wizard' will appear. On this dialog, click 'Next' twice, then specify the .CER file name, then click 'Finish'.
If you still are seeing the same error message, it could be caused by the following:
1) The system may cache the certificate validation results for some time.
The cache is per-process. Thus, you may need to restart the Administration Service after you made changes to the Trusted Root Certificate Authorities store.
2) Group Policy may be configured in a way that prevents locally installed trusted root CAs from working.
Specifically, 'Certificate Path Validation Settings' Group Policy setting may enforce a number of constraints on the locally installed trusted root CAs, and may also enforce general constraints on root CAs.