From what I can see, many people have stumbled upon (aka experienced) this beeing logged in the Event Log (Application) on servers hosting AOS instances. I also see this beeing logged especially on AOS servers hosting AOS instances handling Enterprise Portal and Enterprise Search load, but also on other AOS servers (more sporadic).
Some relevant examples:
Services, service operations, and service groups [AX 2012] and About role-based security in services and AIF [AX 2012] on TechNet.
My hypotese is that AX simply reports back Failed to Logon instead of a more informative description pointing to missing Privilegies or Duties.
All comments are welcomed to share some experience and reach a final solution for this rather hard to diagnose issue (no information about which Service except it's an AIF Document Service and what user is Failing to Logon to AX).
WCF Tracing could perhaps reveal the AIF Document Service and User (I have not looked at this yet), but Exception Logging will not catch this (the issue happens before the actual Message reaches the Queue in AX).
The only solution I would not recommend of the ones I have seen suggested, is to add the Business Connector Proxy User (System Account) as a User in AX. Why? This is a privileged user account in AX and the fact that it's covered by a specific form in AX, should tell you that this account should not be treated as a normal user in AX...