A chave que notei está no um bit para saber se a recursão é desejada. Conforme o link e o RFC 1035 na página 25:
Recursion Desired - this bit may be set in a query and is copied into the response.
If RD is set, it directs the name server to pursue the query recursively.
Recursive query support is optional."
No início, não achei que esse bit fosse a origem do problema, pois às vezes recebia a resposta certa sem o bit set (ou seja, com 0 para recursão). A explicação é que, se um resolvedor tiver um resultado em cache, ele o retornará mesmo com 0 para recursão.
Após algumas conversas na linha de comando, eu simulei meu comportamento com Dig passando o sinalizador "+ norecurse":
$ dig mx google.com @8.8.8.8 +norecurse
; <<>> DiG 9.8.3-P1 <<>> mx google.com @8.8.8.8 +norecurse
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 62530
;; flags: qr ra; QUERY: 1, ANSWER: 0, AUTHORITY: 0, ADDITIONAL: 0
;; QUESTION SECTION:
;google.com. IN MX
;; Query time: 50 msec
;; SERVER: 8.8.8.8#53(8.8.8.8)
;; WHEN: Mon Dec 24 19:52:23 2012
;; MSG SIZE rcvd: 28
Eu então removi o + norecurse e tudo funcionou bem!
Lição: Se você não estiver vendo nenhuma seção de resposta para suas solicitações de DNS, verifique se está realizando uma consulta recursiva. As chances são de que você não é e não há resultados em cache com o seu resolvedor que você está consultando, então você não recebe nada de volta.