Logon failure: unknown user name or bad password. When running "Verify recovery project settings" (4282222)

When local account is specified for Backup Location Access you might encounter following error in UI.

Logon failure: unknown user name or bad password.

FRRestoreService64.log from the DC will contain following text:

Feb 22    10:09:53.261    [8400:3524]     Info        File Access User: Servername\LocalFRMAccount
Feb 22    10:09:53.261    [8400:3524]     Info        Mapping share: '\\Servername\E$\'
Feb 22    10:09:55.866    [8400:3524]    Debug        CNetworkMapShare::Map() map status 53
Feb 22    10:09:55.866    [8400:3524]     Info        FindAccessiblePath failed by invalid creds
Feb 22    10:09:55.866    [8400:3524]     Info    Exit    ExponentialBackoffRetryer::RetryInternal (uncaught exception)
Feb 22    10:09:55.866    [8400:3524]     Info    <<<<     CFileAccess::FindAccessiblePath (uncaught exception)
Feb 22    10:09:55.866    [8400:3524]     Info        Event: Cannot access the backup file.
Feb 22    10:09:55.866    [8400:3524]     Info        Event: Cannot access the backup file '\\DC.domain.local\E$\DC-Backups\Weekly\dcname.local\2019-02-18 03-00-02.bkf'.
Feb 22    10:09:55.866    [8400:3524]     Info        Event: The test operation has failed. Details: Logon failure: unknown user name or bad password.
Feb 22    10:09:55.866    [8400:3524]     Info    >>>>     CFileAccess::DeleteDummy
Feb 22    10:09:55.866    [8400:3524]     Info        Temporary file was not created