A melhor resposta para este problema parece ser um roteador com bugs.
Para depurar este problema, eu configurei minha máquina como um roteador de encaminhamento (alvo TEE do iptables) e configurei a rota padrão no telefone para a minha máquina.
Eu consigo acessá-lo.
E agora, quando eu mudar a rota padrão novamente no meu telefone para o meu roteador, ele começa a funcionar.
Extremamente estranho.