The key that I noticed is in the one bit for whether recursion is desired. As per http://www.ietf.org/rfc/rfc1035.txt and RFC 1035 at page 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."
At first, I didn't think this bit was the source of the problem as I sometimes received the right response without the bit set (i.e., with 0 for recursion). The explanation is that if a resolver has a result cached, it will return it even with 0 for recursion.
After some playing around at the command-line, I simulated my behavior with Dig by passing the "+norecurse" flag:
$ dig mx google.com @22.214.171.124 +norecurse
; <<>> DiG 9.8.3-P1 <<>> mx google.com @126.96.36.199 +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: 188.8.131.52#53(184.108.40.206)
;; WHEN: Mon Dec 24 19:52:23 2012
;; MSG SIZE rcvd: 28
I then removed the +norecurse and everything worked fine!
Lesson: If you are not seeing any answer section to your DNS requests, check whether you are performing a recursive query. Chances are you are not and there are no cached results with your resolver you are querying, so you get nothing back.