Ok, eu finalmente resolvi o problema usando pura e simples sorte e persistência.
Eu perdi o link, mas através de muitas pesquisas eu entrei em um site russo (traduzido para o inglês pelo Google) onde as pessoas tinham problemas semelhantes com uma série de roteadores TP-Link, a mesma marca do meu provedor fornecido para mim.
A solução foi baixar o MTU do seu padrão de 1500 para 1400. Talvez mais alto funcione, mas hoje acredito em "Não conserte o que não está quebrado"
Espero que isso ajude alguém: -)