CPUU error, "MAPI_E_LOGON_FAILED" (4350336)

CPUU has been configured to use service accounts to update user profiles (not end-user credentials), but is not able to update the user's Outlook profile. When reviewing the CPUU logs, the following error can be seen:

5/3/2017 1:24:43 PM 5072   [Trace]           Open store 'Private Folders'.
MAPI result: 0x80040111, Description: MAPI_E_LOGON_FAILED, Extended info: Component: MAPI 1.0, Description: The information store could not be opened., Context: 646, Low level: 0
Stack: 0046A22A 004D766B 004D1B83 004D1844 005B0F66 005A7193 005C43E8 005C21BA 00428D1D 0042859C 00437E20 00623C41 BaseThreadInitThunk RtlInitializeExceptionChain RtlInitializeExceptionChain