I am trying to execute SPWeb.EnsureUser (SharePoint 2013) method inside a service called by the nintex workflow. I am getting an Unauthorized operation exception. If I surround the code with RunWithElevatedPrivilages everything is working fine. However, this should be working also without this... The workflow runs with a farm administrator privileges. My service is created by this factory: MultipleBaseAddressBasicHttpBindingServiceHostFactory Class:

[BasicHttpBindingServiceMetadataExchangeEndpoint]public class MyService : IMyService

The method:

[OperationContract]
[WebInvoke(Method = "POST",
   BodyStyle = WebMessageBodyStyle.Bare,
   RequestFormat = WebMessageFormat.Xml,
   ResponseFormat = WebMessageFormat.Xml)]
string Test(string a);

Inside the method, I have only this EnsureUser and I am returning some dummy value. I am executing this by using a Nintex Call Web Service block with credentials of the farm administrator. Exceptions:

Non-OAuth request. IsAuthenticated=False, UserIdentityName=, ClaimsCount=0

System.UnauthorizedAccessException: Access is denied. (Exception from HRESULT: 0x80070005 (E_ACCESSDENIED)), StackTrace: 
 at Microsoft.SharePoint.SPUser.InitMember() 
 at Microsoft.SharePoint.SPUser..ctor(SPWeb web, SPSecurableObject scope, String strIdentifier, ObjectO,] arrUsersData, UInt32 index, Int32 iByParamId, String strByParamSID, String strByParamEmail, SPUserCollectionType userCollectionType, SPUserCollectionFlags ucf, Boolean isSiteAuditor) 
 at Microsoft.SharePoint.SPUserCollection.GetByLoginNoThrow(String loginName, SPUserCollectionFlags ucf) 
 at Microsoft.SharePoint.SPWeb.EnsureUser(String logonName) 
 at <MY_code_here> 
 at SyncInvokeAddRoutingHistoryDetail(Object , ObjectO] , ObjectO] ) 
 at System.ServiceModel.Dispatcher.SyncMethodInvoker.Invoke(Object instance, ObjectO] inputs, ObjectO]& outputs) 
 at System.ServiceModel.Dispatcher.DispatchOperationRuntime.InvokeBegin(MessageRpc& rpc) 
 at System.ServiceModel.Dispatcher.ImmutableDispatchRuntime.ProcessMessage5(MessageRpc& rpc) 
 at System.ServiceModel.Dispatcher.ImmutableDispatchRuntime.ProcessMessage11(MessageRpc& rpc) 
 at System.ServiceModel.Dispatcher.MessageRpc.Process(Boolean isOperationContextSet) 
 at System.ServiceModel.Dispatcher.ChannelHandler.DispatchAndReleasePump(RequestContext request, Boolean cleanThread, OperationContext currentOperationContext) 
 at System.ServiceModel.Dispatcher.ChannelHandler.HandleRequest(RequestContext request, OperationContext currentOperationContext) 
 at System.ServiceModel.Dispatcher.ChannelHandler.AsyncMessagePump(IAsyncResult result) 
 at System.ServiceModel.Dispatcher.ChannelHandler.OnAsyncReceiveComplete(IAsyncResult result) 
 at System.Runtime.Fx.AsyncThunk.UnhandledExceptionFrame(IAsyncResult result) 
 at System.Runtime.AsyncResult.Complete(Boolean completedSynchronously) 
 at System.Runtime.InputQueue`1.AsyncQueueReader.Set(Item item) 
 at System.Runtime.InputQueue`1.EnqueueAndDispatch(Item item, Boolean canDispatchOnThisThread) 
 at System.Runtime.InputQueue`1.EnqueueAndDispatch(T item, Action dequeuedCallback, Boolean canDispatchOnThisThread) 
 at System.ServiceModel.Channels.SingletonChannelAcceptor`3.Enqueue(QueueItemType item, Action dequeuedCallback, Boolean canDispatchOnThisThread) 
 at System.ServiceModel.Channels.HttpPipeline.EnqueueMessageAsyncResult.CompleteParseAndEnqueue(IAsyncResult result) 
 at System.ServiceModel.Channels.HttpPipeline.EnqueueMessageAsyncResult.HandleParseIncomingMessage(IAsyncResult result) 
 at System.Runtime.AsyncResult.SyncContinue(IAsyncResult result) 
 at System.ServiceModel.Channels.HttpPipeline.EmptyHttpPipeline.BeginProcessInboundRequest(ReplyChannelAcceptor replyChannelAcceptor, Action dequeuedCallback, AsyncCallback callback, Object state) 
 at System.ServiceModel.Channels.HttpChannelListener`1.HttpContextReceivedAsyncResult`1.ProcessHttpContextAsync() 
 at System.ServiceModel.Channels.HttpChannelListener`1.BeginHttpContextReceived(HttpRequestContext context, Action acceptorCallback, AsyncCallback callback, Object state) 
 at System.ServiceModel.Activation.HostedHttpTransportManager.HttpContextReceived(HostedHttpRequestAsyncResult result) 
 at System.ServiceModel.Activation.HostedHttpRequestAsyncResult.HandleRequest() 
 at System.ServiceModel.Activation.HostedHttpRequestAsyncResult.BeginRequest() 
 at System.ServiceModel.Activation.HostedHttpRequestAsyncResult.OnBeginRequest(Object state) 
 at System.ServiceModel.AspNetPartialTrustHelpers.PartialTrustInvoke(ContextCallback callback, Object state) 
 at System.ServiceModel.Activation.HostedHttpRequestAsyncResult.OnBeginRequestWithFlow(Object state) 
 at System.Runtime.IOThreadScheduler.ScheduledOverlapped.IOCallback(UInt32 errorCode, UInt32 numBytes, NativeOverlapped* nativeOverlapped) 
 at System.Runtime.Fx.IOCompletionThunk.UnhandledExceptionFrame(UInt32 error, UInt32 bytesRead, NativeOverlapped* nativeOverlapped) 
 at System.Threading._IOCompletionCallback.PerformIOCompletionCallback(UInt32 errorCode, UInt32 numBytes, NativeOverlapped* pOVERLAP) 

If I disable Anonymous Authentication in IIS then WF cannot call the webservice. Looks like this block is not sending any authentication tokens etc...