Git gives 'ERROR: Repository not found.' when URL is correct and SSH key is used

I had a fun problem that made me spin my wheels an hour or so today. I was having no issue cloning a remote repository a number of times in the morning while debugging a Jenkins build job that runs a git clone + Docker image build and push operation.

Suddenly, when I was doing some final testing, I started to get the following:

git clone [email protected]:geerlingguy/my-project.git                            
Cloning into 'my-project'...
ERROR: Repository not found.
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

I know that I had the repository's SSH key loaded (via eval "$(ssh-agent -s)" && ssh-add ~/.ssh/deploy-key), and if I unloaded the key, I would instead get:

Cloning private GitHub repositories with Ansible on a remote server through SSH

One of Ansible's strengths is the fact that its 'agentless' architecture uses SSH for control of remote servers. And one classic problem in remote Git administration is authentication; if you're cloning a private Git repository that requires authentication, how can you do this while also protecting your own private SSH key (by not copying it to the remote server)?

As an example, here's a task that clones a private repository to a particular folder:

- name: Clone a private repository into /opt.
    repo: [email protected]:geerlingguy/private-repo.git
    version: master
    dest: /opt/private-repo
    accept_hostkey: yes
  # ssh-agent doesn't allow key to pass through remote sudo commands.
  become: no

If you run this task, you'll probably end up with something like: