Eu descobri qual era o problema.
Depois de muito tempo lutando para descobrir o que havia de errado com o resolvconf ou dnsmasq, finalmente decidi verificar novamente o firewall. Como eu não mudei nada nas regras do iptables por 5 anos, não achei que esse seria o problema. Mas eu não conseguia descobrir por que o dnsmasq estava escutando na porta 53, mas não escrevia nenhuma pesquisa de DNS em seus logs. Então tinha que ser o firewall.
Há algum tempo, escrevi uma regra para permitir que tudo isso não fosse da interface externa.
iptables -A INPUT -i !eth0 -j ACCEPT
Isso funcionou bem na antiga máquina que eu tinha porque não estava usando o dnsmasq para pesquisas de DNS no servidor real. Então, o dnsmasq trabalhou alegremente em solicitações recebidas na eth1. Mas na minha nova máquina, comecei a testá-lo com look-ups. Com o Ubuntu 12.04, essa regra não permite "todas as interfaces, exceto a eth0". Eu brinquei com a regra e achei que deveria ser isso:
iptables -A INPUT ! -i eth0 -j ACCEPT
Talvez se eu tivesse colocado a hora do trabalho de volta no início para configurar minha nova máquina com o ufw, eu teria sido instalado e executado no mesmo dia. Coulda woulda shoulda ....