CPUU fails with error code 0x8004011d "The Microsoft Exchange Server computer is not available (4262480)

EMWProf fails to update the profile, with errors upon connecting to the Exchange server such as the following:

04/12/2008 14:03:37 SM [Warning] Cannot open the message store Public Folders.

MAPI error.
Error code: 0x8004011d
Extended error description:
Component: Microsoft Exchange Server Information Store
Error description: The Microsoft Exchange Server computer is not available. Either there are network problems or the Microsoft Exchange Server computer is down for maintenance.
Context: 1318
Low level: 2147746069

It is possible to connect to both the source and target Exchange servers from the client machine under the same security context as EMWProf is running when using both MFCMAPI and Outlook, but these programs prompt for credentials before granting access.