MAPILogonEx 80040111 from WCF application

I am trying to use the MAPI libraries from a WCF service application under the LocalService identity, but keep on getting the 0x80040111 MAPI_E_LOGON_FAILED error.

As suggested by https://support.microsoft.com/en-us/kb/181739, I have enabled Log on locally for the given user.

Do you know where could this be coming from?