How to fix EWS trouble in Lync 2013 when it works for some users

I have been together With some coworkers where we have Exchange in Office365 (Exchange Online) and Lync On-Premise.
We had some issue where some had all presence information and Exchange EWS working just fine, but for some it has stopped working.


The error we got was this:
StoreWebException: code=ErrorEwsAutodiscover, reason=GetUserSettings failed, smtpAddress=user@domain.com, Autodiscover Uri=https://autodiscover.domain.com/autodiscover/autodiscover.svc, Autodiscover WebProxy=<NULL>, WebExceptionStatus=ConnectFailure ---> System.Net.WebException: Unable to connect to the remote server ---> System.Net.Sockets.SocketException: No connection could be made because the target machine actively refused it.
To solve this we did not find any good help on the different forums. So solve this we did the following for this issue.

Solution

First we did was to delete the Outlook profile in %USERPROFILE%\AppData\Local\Microsoft\Outlook.
This meens you have to shut down Outlook to make this. Then create a new userprofile for OutLook. Then you will see that EWS is now OK in Lync Configuration, but it did not work either. Then we deleted the Lync login information, and then we got it working.