cannot import PnP.PowerShell module from the pwsh.exe terminal

[IndYank310]

Hi there,
I hope you're doing well. I'm reaching out because we're facing an issue that I hope you can assist with. We have a service that uses PowerShell scripts to create Teams and add members to them within our tenant. It has been running smoothly since we first set it up back in 2018. However, since the change on September 9, the service is now broken, and we’re getting the following error:
“Application with identifier '31359c7f-bd7e-475c-86db-fdb8c937548e' was not found in the directory 'The [companyname]'.”
I followed the instructions mentioned here: #4250.

Here’s what I’ve done so far:
• Installed PowerShell 7.4.5 on my server (this is my first time using PowerShell 7 :-) ).
• Uninstalled all previous versions of PnP.PowerShell.
• Installed the latest version at the time: 2.12.18-nightly using the command:
Install-Module PnP.PowerShell -Scope AllUsers -AllowPrerelease -SkipPublisherCheck
• Set up access to our own Entra ID App for App Only Access as per the instructions and saved the certificates under C:\ as instructed.
This was done by running the Register-PnPEntraIDApp command.
So far so good. I then try to connect. My connection command looks like this:
connect-pnponline -Url $PSurl -ClientId $ClientID -Tenant $Tenant -CertificatePath $CertPath -ReturnConnection

But here comes my issue:
This works fine when I run it from Visual Studio Code, but when I try running it by calling C:\Progra~1\PowerShell\7\pwsh.exe, I keep getting the following error:
connect-pnponline: The 'connect-pnponline' command was found in the module 'PnP.PowerShell', but the module could not be loaded due to the following error: [Could not load file or assembly 'Microsoft.SharePoint.Client, Version=16.1.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c'. Could not find or load a specific file. (0x80131621)]

I also tried running Import-Module PnP.PowerShell and got this error:
Import-Module: Could not load file or assembly 'Microsoft.SharePoint.Client, Version=16.1.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c'. Could not find or load a specific file. (0x80131621)

I would really appreciate any guidance or suggestions on how to resolve this issue. I need to get the service running again as soon as possible.
Thank you so much for your time and help!
Best regards
Ido