I'm wondering if the problem has something to do with TCP retransmissions exploding the number of DNS requests. In the iodine client terminal there was a continuous flow of DNS requests and (most of the time) answers, so the communication at that level was kind-of working... but at the SSH level, it was practically unusable.