the "real" ssh uses the .ssh directory that is located under the "home" which is determined from getpwuid(get[e?]uid()). On the other hand, paramico apparently consults the $HOME/.ssh/known_hosts. And if you changed $HOME (which I did in the cronjob script) paramico does not find the known_hosts file.
By the way, the message that is issued in this case is rather confusing:
ssh connection to x failed: Unknown server x
which looks as if it could not resolve the server name. It would be much better if it said "No public key known for server x" or something like that.
Related duplicity bug: https://bugs.launchpad.net/duplicity/+bug/965017
Changelog re #66, re #141. Fixes #66