psftp says "The server's host key is not cached in the registry"

I'm getting the following message when trying to connect to an SFTP server from PowerShell using psftp:

Error:

psftp.exe : The server's host key is not cached in the registry. You have no guarantee that the server is the computer you think it is.
The server's rsa2 key fingerprint is:ssh-rsa 2048 41289438190410491
Connection abandoned.

PowerShell script:

$Username = "Username"
$Password = "Password"

psftp.exe sftpserver -l $Username -pw $Password -batch -bc -b C:\batch\download.bat

(psftp.exe is stored in c:\windows\system32)

I've SSH into this server from this server before via PuTTY and WinSCP without issue. However, it won't connect when running via PowerShell.

That message is not an error.

Every SSH/SFTP client needs to verify a host key of a server.

Even PuTTY and WinSCP asked you for sure on your first connection to the server to verify a host key.

Though PuTTY and psftp share a host key cache. Are you sure you used PuTTY on the same machine with the same local Windows account?

Anyway, either:

• Run psftp once without the -batch switch. Check the host key and confirm if you trust it. psftp will cache the host key and will work from now on.
• Or add -hostkey switch with a fingerprint of trusted hostkey to your psftp command in PowerShell script.

See also Respond y(es) to psftp host key prompt (though the highest-scored answer by @vmitchell85 is wrong, see the answer by @GerriePretorius).