Xxx (app) can't be opened because the identity of the developer cannot be confirmed

I am not a developer directly, but I have a website that has a 3rd party application.

We just finished updating the Application to 64 bits in preparation for macOS Catalina.

The app was code signed with a Developer ID. I've confirmed when installed it IS from an Identified Developer (from System Preferences > Applications > App. The certificate doesn't expire until 2024.

The first few customers had no problems with using the Application. Now suddenly they are getting the error:

"Xxx (app) can't be opened because the identity of the developer cannot be confirmed."

Does anyone know what to do from a developer perspective? How can I confirm the identity? What is the procedure to confirm identity.

I know the app can be opened by control + click, but I'm trying to make this smoother for my customers and ideally this message can be resolved fully.

I just tried speaking to a human at Apple and after 27 minutes on hold, I was hung up on.

Anyone knowledgeable in this from a developer perspective?

Thanks in advance.