Symptoms

The following errors are reported during Exchange EWS restore (Message level Restore).

10110085: Failure in creating new mailbox :info@assurestor.local
10110039 : The following exception has occurred. The WinRM service cannot process the request because the request needs to be sent to a different machine. Use the redirect information to send the request to a new machine.
10110073 : Retry count exceeded. Could not connect to Exchange Online. 

Cause

The Exchange server does not have Powershell authentication enabled.

Workaround

Perform the following steps then run the restore again.
-Open the Exchange Admin Center and Click on Servers
-Choose the Virtual Directories tab -Click on Powershell (Default Web Site) or Powershell (Exchange Web Services web site)
-Choose authentication -Enable "Basic Authentication"