That error usually occurs if you have at some point changed the service account password, which might explain why the credentials still work but are failing later.
The documentation mentions that there are two things that need to be done when you change the service account password.
First, you need to change the password under the Windows Service Control Manager. Until this issue is resolved you will see following errors:
If you try to start the Synchronization Service in Windows Service Control Manager, you receive the error "Windows could not start the Microsoft Azure AD Sync service on Local Computer". Error 1069: The service did not start due to a logon failure."
Under Windows Event Viewer, the system event log contains an error with Event ID 7038 and message “The ADSync service was unable to log on as with the currently configured password due to the following error: The user name or password is incorrect."
Second, under specific conditions, if the password is updated, the Synchronization Service can no longer retrieve the encryption key via DPAPI. Without the encryption key, the Synchronization Service cannot decrypt the passwords required to synchronize to/from on-premises AD and Azure AD. You will see errors such as:
Under Windows Service Control Manager, if you try to start the Synchronization Service and it cannot retrieve the encryption key, it fails with error “Windows could not start the Microsoft Azure AD Sync on Local Computer. For more information, review the System Event log. If this is a non-Microsoft service, contact the service vendor, and refer to service-specific error code -21451857952.”
Under Windows Event Viewer, the application event log contains an error with Event ID 6028 and error message “The server encryption key cannot be accessed.”
To ensure that you do not receive these errors, follow the procedures in Abandoning the ADSync service account encryption key when changing the password.
If you haven't done so already I would try following the troubleshooting guide for this error and try those two steps.