Eu recebi uma resposta do desenvolvedor do n2n, então estou postando aqui.
O que eu observo é uma conseqüência de nós não conseguirem estabelecer conexão P2P. Isso ocorre porque o encapsulamento reverso do UDP é bloqueado em algum estágio. Nesse caso, o tráfego recua a um caminho que envolve supernós.
Quanto às alternativas, isso é o que eu encontrei (não testado):