Exchange 2013 cannot send mails from some (not all!) clients

I have a strange problem with Exchange 2013.

I'm using an Wildcard certificate for ex-01.internal.company.nl, this is also the internal + external server name for this machine.

The Remote Connectivity Analyzer from Microsoft completes with only a warning that the trust MIGHT not be valid for older versions of windows if the 'update root certificates' is not enabled. So that should not cause any issues on Windows 7 or 8.

2 Clients have the same problem, causing them to be unable to SEND mail. No problems with Receiving the mails. Sending mail causes an error:

Task 'mailbox@company.nl - Sending' reported error (0x80040115) : 'We can't complete this because we can't contact the server right now. Please try again later.'

The auto discovery is all configured correctly and is working.

The problem can be solved on one client by fiddling with the "USE SSL" or not (from time to time you need to clear or recheck the SSL checkbox.)

On the Other PC, the only thing that seems to be working is to delete the Outlook profile, create a new one and it works.... for both the clients, the problems will re-occur the next day.

Some configuration data:

Get-ClientAccessServer | ft identity,AutodiscoverServiceInternalUri

Identity           AutoDiscoverServiceInternalUri
--------           ------------------------------
EX-01              https://ex-01.intern.company.nl/Autodiscover/Autodis...


Get-WebServicesVirtualDirectory | ft identity,internalurl

Identity                            InternalUrl
--------                            -----------
EX-01\EWS (Default Web Site)        https://ex-01.intern.company.nl/EWS/Exchange.asmx

Get-OabVirtualDirectory | ft identity,internalurl

Identity                                                    InternalUrl
--------                                                    -----------
EX-01\OAB (Default Web Site)                                https://ex-01.intern.company.nl/OAB

Get-OwaVirtualDirectory | ft identity,internalurl

Identity                                                    InternalUrl
--------                                                    -----------
EX-01\owa (Default Web Site)                                https://ex-01.intern.company.nl/owa

Get-ECPVirtualDirectory | ft identity,internalurl

Identity                                                    InternalUrl
--------                                                    -----------
EX-01\ecp (Default Web Site)                                https://ex-01.intern.company.nl/ecp

Get-ActiveSyncVirtualDirectory | ft identity,internalurl

Identity                                                    InternalUrl
--------                                                    -----------
EX-01\Microsoft-Server-ActiveSync (Default Web Site)        https://ex-01.intern.company.nl/Microsoft-Server-Act...


Get-OutlookAnywhere

RunspaceId                         : e29d0f47-c138-45b6-86c2-82e4b8052bd5
ServerName                         : EX-01
SSLOffloading                      : True
ExternalHostname                   : ex-01.intern.company.nl
InternalHostname                   : ex-01.intern.company.nl
ExternalClientAuthenticationMethod : Negotiate
InternalClientAuthenticationMethod : Ntlm
IISAuthenticationMethods           : {Basic, Ntlm, Negotiate}
XropUrl                            :
ExternalClientsRequireSsl          : True
InternalClientsRequireSsl          : True
MetabasePath                       : IIS://EX-01.intern.company.nl/W3SVC/1/ROOT/Rpc
Path                               : C:\Program Files\Microsoft\Exchange Server\V15\FrontEnd\HttpProxy\rpc
ExtendedProtectionTokenChecking    : None
ExtendedProtectionFlags            : {}
ExtendedProtectionSPNList          : {}
AdminDisplayVersion                : Version 15.0 (Build 516.32)
Server                             : EX-01
AdminDisplayName                   :
ExchangeVersion                    : 0.20 (15.0.0.0)
Name                               : Rpc (Default Web Site)
DistinguishedName                  : CN=Rpc (Default Web Site),CN=HTTP,CN=Protocols,CN=EX-01,CN=Servers,CN=Exchange Adm
                                     inistrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=Company,CN=Mi
                                     crosoft Exchange,CN=Services,CN=Configuration,DC=intern,DC=company,DC=nl
Identity                           : EX-01\Rpc (Default Web Site)
Guid                               : 733277a8-8ac0-47a9-992d-4290fe1fc863
ObjectCategory                     : intern.company.nl/Configuration/Schema/ms-Exch-Rpc-Http-Virtual-Directory
ObjectClass                        : {top, msExchVirtualDirectory, msExchRpcHttpVirtualDirectory}
WhenChanged                        : 23-7-2014 16:15:37
WhenCreated                        : 7-2-2014 15:00:59
WhenChangedUTC                     : 23-7-2014 14:15:37
WhenCreatedUTC                     : 7-2-2014 14:00:59
OrganizationId                     :
OriginatingServer                  : DC-01.intern.company.nl
IsValid                            : True
ObjectState                        : Changed


Get-ExchangeCertificate

Thumbprint                                Services   Subject
----------                                --------   -------
BD814E2F6CCA8B2C976B0123378961D79E5727E4  ...WS..    CN=*.intern.company.nl, OU=PositiveSSL Wildcard, OU=Do
2C0FF06076E38DE77778E4391C1607DCC618D7DF  .......    CN=*.company.nl, OU=PositiveSSL Wildcard, OU=Domain Co
7A3F5779CF9A7F243F29BDD4BE0C5FC366A54DA5  ....S..    CN=Microsoft Exchange Server Auth Certificate
3A957CA8CC9C0B8457B2B3C6D1D3D39D93B11B75  IP.WS..    CN=EX-01
BB36FB14C6437CEEAA187B8D172EAE4240C9FE84  .......    CN=WMSvc-EX-01

I'm completely out of ideas, nothing I found on the internet until now has proven to be a working solutions. (At least not a permanent solution.)

Maybe anybody has some new ideas which I forgot to check?

I did install CU6 a few months ago and the problem did not occur since.

So for those to who it might apply, install the latest update.