Automated Backup for SQL VMs "Key not valid for use in specified state."

In Azure, when enabling Automated backups for SQL virtual machine (MS SQL in a VM), the operation fails. Similar errors occur with Azure Backup for SQL VMs.

The Azure Portal reports:

{
    "status": "Failed",
    "error": {
        "code": "Ext_AutomatedBackupError",
        "message": "Error: 'Key not valid for use in specified state.\r\n'"
    }
}

These three events in the event log:

Source      Microsoft SQL Server Automated Backup
Event       57052

Message
[Warning] ManagedBackupConfigureFailed: System.Exception: Configuring auto backup failed ---> System.Security.Cryptography.CryptographicException: Key not valid for use in specified state.

   at System.Security.Cryptography.Pkcs.EnvelopedCms.DecryptContent(RecipientInfoCollection recipientInfos, X509Certificate2Collection extraStore)
   at Microsoft.SqlServer.Management.IaaSUtility.EncryptionUtility.DecryptSecureString(SecureString encryptedValue, String thumbprint, StoreName storeName, StoreLocation storeLocation)
   at Microsoft.SqlServer.Management.AutoBackup.ManagedBackupManagement.UpdateConfigurations(SecureString protectedSettingsCertificateThumbprint, SecureString protectedSettings, PublicSettings publicSettings)
   --- End of inner exception stack trace ---

2nd:

Source      Microsoft SQL Server IaaS Agent
Event       56050

Message
[Warning] IaaSHandlerConfigurationUpdateError: System.Exception: Failed to update configuration ---> System.Security.Cryptography.CryptographicException: Key not valid for use in specified state.

   at System.Security.Cryptography.Pkcs.EnvelopedCms.DecryptContent(RecipientInfoCollection recipientInfos, X509Certificate2Collection extraStore)
   at Microsoft.SqlServer.Management.IaaSUtility.EncryptionUtility.DecryptSecureString(SecureString encryptedValue, String thumbprint, StoreName storeName, StoreLocation storeLocation)
   at Microsoft.SqlServer.Management.AutoBackup.ManagedBackupManagement.UpdateConfigurations(SecureString protectedSettingsCertificateThumbprint, SecureString protectedSettings, PublicSettings publicSettings)
   at Microsoft.SqlServer.Management.AutoBackup.AutoBackupManagement.UpdateConfigurations(Int32 configurationSequenceNumber, SecureString protectedSettingsCertificateThumbprint, SecureString protectedSettings, PublicSettings publicSettings)
   at Microsoft.SqlServer.Management.SqlIaaSHandler.IaaSHandler.NewConfigurationFileFound(Object sender, NewFileEventsArgs e)
   --- End of inner exception stack trace ---

3rd:

Source      Microsoft SQL Server Management
Event       60629

Message
[Warning] ServerConfigurationManagementDeserializePrivateSettingsFailed: System.Exception: Deserializing protected settings to get SQL password failed. ---> System.Security.Cryptography.CryptographicException: Key not valid for use in specified state.

   at System.Security.Cryptography.Pkcs.EnvelopedCms.DecryptContent(RecipientInfoCollection recipientInfos, X509Certificate2Collection extraStore)
   at Microsoft.SqlServer.Management.IaaSUtility.EncryptionUtility.DecryptSecureString(SecureString encryptedValue, String thumbprint, StoreName storeName, StoreLocation storeLocation)
   at Microsoft.SqlServer.Management.ServerConfigurationsManagement.ServerConfigurationsPluginManager.DeserializePrivateSettings(SecureString protectedSettingsCertificateThumbprint, SecureString protectedSettings, Boolean isExtensionTestOnly, String& userName, String& password)
   --- End of inner exception stack trace ---

How can this be fixed?