I had the same problem last week, but only on projects with a private repo defined in repositories.
I think the problem started after updating my github personal access token to the new format.
I fixed it by logging in to the remote server with ssh with the web user and running composer install from one of the failed deploy release folders. I will prompt a github message that you need to enter a personal access token for composer.
Follow these instructions (or copy your local token from your global composer config) and enter the token, the error will be gone on the next deploy!