Workflow 401 unauthorized error when calling SharePoint 2013 based WCF web service.

Update: the issue is fixed with the March Update of SharePoint 2013. Install it, re-register your workflow and the problem should be gone. As discussed here.

SharePoint 2013 no longer allows SharePoint developers to create custom coded workflows in Visual Studio. Instead we must now create web services that we call from a workflow with the http workflow action.

So this is what I did, create a custom wcf in Visual Studio 2012 and deployed it to my farm. After a bit of effort I was eventually able to get it to work and could see a response to my web service call from multiple web browsers (as multiple different users).

Whoever when I tried to consume the web service in a workflow I confronted with a 401 Unauthorized error. I Googled and found a many suggestions, mostly from older version of SP:

1. Loop-back issues? Nope, my registry was already changed.
2. Run C+ code with elevated privileges? Not valid, My service returns a simple string.
3. Set Header to Authentication="". Didn't have any effect.
4. Run in App Step? No effect.
5. Enable anonymous in the web application...

I was rather reluctant to enable anonymous but unfortunate it turned out to be necessary to allow Workflow Manager to makes calls to my custom web service. 

Before you go...

Enabling Anonymous is the first but there are two spots to control anonymous access in a web application, and you might want to consider the second one also.

For both steps: open Central administration and navigate to: Application management > Manage web applications.

To Enable Anonymous access: Click/highlight a web application row > Authentication Providers > Click 'Default'. Tick Enable anonymous access.

Your web service will now work but...

Set Policy: Click/highlight a web application row > Anonymous Policy. I discovered that if you select "Deny All - Has no access" the web service calls will still work! 

Theoretically this means anonymous access is now off again but I can still make web service calls. I do not claim to know exactly what is going on here but this seems to fit my need perfectly: anonymous access denies but web service enabled, so I will take the win.

Please feel free comment on this querk if you are knowledgeable on the subject.