Encontrei uma solução depois de longas horas de tentativas. A solução é muito simples e aparentemente muito estúpida, mas funciona (por isso não é estúpido).
A resposta do @Tyson foi uma boa dica. Também encontrei uma resposta semelhante no Google, por isso supus que esta é uma pista certa.
Se eu não consegui mudar o IP da impressora para 192.168.0.x, fiz um inverso . Eu mudei o IP do roteador de 192.168.0.1 para 10.0.0.0 e ele funciona ... :) "DHCP Clients" encontra; lembre-se também de iniciar os IPs dos PCs um pouco mais se você tiver uma opção semelhante (meu PC-IP inicial é agora 10.0.0.10).
É isso, simples assim. Não é necessário "comprar nova impressora" nem nada. Funciona como um encanto.
// --------------------------------------------- ------------
EDIT: coisas importantes!
A impressora funciona como um encanto, mas a mudança de IP da rede resultou em problemas aleatórios de internet em alguns dispositivos (claro que eu reconfigurei todos eles, mas aleatoriamente alguns dispositivos estavam funcionando, alguns não, e alguns estavam trabalhando às vezes e muito lento).
Como corrigir?
1) Mude o IP do roteador para 10.0.x.x como escrevi antes.
2) Por fim, consegui acessar as configurações da impressora (escreva 10.0.0.3 no navegador), configure a impressora para 192.168.x.x ou qualquer coisa que você queira.
3) Reconfigure o IP do roteador para 192.168.x.x
A impressora funciona, todos os dispositivos funcionam agora.