scp foo user@remote:bar works fine

scp user@remote:foo bar works fine

scp user@remote:foo user@remote:bar fails with error:

Host key verification failed.
lost connection

I am guessing this is because scp disallows remote to remote copy (between two different remote hosts or the same remote host) because it is inefficient to channel the data from point A to point L to point B rather than directly from point A to point B.

Is that the right rationale for why it doesn't work? How come the command-line usage instructions in the manual does not document it? Or is it just that the specific scp on my Ubuntu distribution is trying to be paternal?

Check out the option:

-3 : Copies between two remote hosts are transferred through the local host. Without this option the data is copied directly between the two remote hosts. Note that this option disables the progress meter.

This option became available in OpenSSH 5.7