IDX10503 Exception with Secret Issued from Partner Center for Store Listed Application (SharePoint Provider hosted addin) - Client Secret is no longer base64 string

Target SharePoint environment

SharePoint Online

What SharePoint development model, framework, SDK or API is this about?

SharePoint Add-ins

Developer environment

Windows

What browser(s) / client(s) have you tested

• 💥 Internet Explorer
• 💥 Microsoft Edge
• 💥 Google Chrome
• 💥 FireFox
• 💥 Safari
• mobile (iOS/iPadOS)
• mobile (Android)
• not applicable
• other (enter in the "Additional environment details" area below)

Additional environment details

No response

Describe the bug / error

I have a Store listed SharePoint Add-in that was created few years ago, and need to update the secret. Yesterday in the morning we created a new client secret and removed old ones from the Partner Portal. New client secret that we get from the Partner Portal is no longer a base64 string and when we replaced ClientSecret in our web.config, we got the following error:
System.FormatException: The input is not a valid Base-64 string as it contains a non-base 64 character, more than two padding characters, or an illegal character among the padding characters.
In order to avoid this issue, we encoded the client secret to base64 string and now we get the following error:
Microsoft.IdentityModel.Tokens.SecurityTokenInvalidSignatureException: 'IDX10503: Signature validation failed. Keys tried: '[PII is hidden]'.

It's already been more than 24 hours since we created new Client Secret, so we believe it should already propagate correctly.
Is the basic encoding to base64 a wrong choice, or what could be a reason for our application not to validate a token properly?
I have also checked the new client secret using Connect-PnPOnline via powershell and without any additional encoding the secret works.

Thanks in advance - as this is about our live application, I would appreciate any help.

Steps to reproduce

1. Locate a SharePoint Store listed, provider hosted add-in, created several years ago.
2. Create a new Secret in Partner Center
3. Update the application with the new secret.

Expected behavior

The expected behaviour is for the JWT token to pass validation correctly.