I tried to connect in a new terminal window–indeed: "no route to host". Some seconds of scratching my head later I tried again. And could login just fine. Ok, some temporary glitch, let's just surf:deploy again. Bummer. The same error.
I now faintly remembered I had seen this before and started to think about possible reasons, ending up at some kind of rate limiting. Surf fires quite a number of SSH commands in rapid succession, after all… The uberspace documentation didn't really mention rate limiting, but Google pointed me to some conversation between an uberspace user and some staff members talking about SSH, Subversion and lots of connections. Update: The uberspace staff pointed me to their FAQ, clearly mentioning it. Oh, well, doh.
So I decided to read up on the mentioned SSH configuration option, even though going to some Subversion forum seemed far fetched. But in the end it solved my issue: ControlMaster to the rescue.
SSH provides a way to reuse an existing SSH connection for subsequent connection attempts to the same host. Sprinkle this with some ~/.ssh/config tweaks and you have not only faster connections if one connection is already open, but also solve the Surf issue I saw. Nice.
So this is how it works:
The first line tells SSH to apply the following settings to connections to myhost.uberspace.de, the machine I had trouble with. The second line enables ControlMaster, while the third line sets a default path to the needed socket. The last line is making sure that disconnecting the first connection doesn't harm other connections for a while and makes things more stable.
First I used Host * but that seemed to cause some side effects with git and SourceTree. I still need to verify that assumption, but for now I am happy with the solution.