The client ID contains the project number. The client ID is constructed the following way:
<PROJECT_NUMBER>-<RANDOM_STUFF>.apps.googleusercontent.com
If you have access to the project, you can access the list of credentials by going to the link https://console.cloud.google.com/apis/credentials?project=<PROJECT_NUMBER>.
In there, you can verify if the client ID has been deleted, and if not, delete it yourself.
You can also check if the project is pending deletion by using the same project number in this command (requires gcloud installed and properly authenticated):
curl -H"Authorization: Bearer $(gcloud auth print-access-token)" -H'Accept: application/json' \
'https://cloudresourcemanager.googleapis.com/v1/projects?filter=projectNumber%3A<PROJECT_NUMBER>'
As per the API definition, if the response has the field "lifecycleState":"DELETE_REQUESTED", it means that the project is pending deletion but still recoverable.
All of these steps are contingent to you having access to the project with the credentials. If you don't have that access, you should find somebody who has. If that project was within an organization, someone with permissions at the organization level should have access to all the projects within.
With all that said, the error does look like it means the client was deleted, and there is no way to recover deleted credentials, at least according to the warning message when deleting one:

The biggest danger I see is that the leaked credentials contain the project number, but abusing only a project number is pretty hard.