Solution:
Here is the final word: my qmail server does an all records request whenever it tries to send for mail... or at least that's what the PIX thinks it is doing. The PIX intrusion detection engine drops the DNS session and kills delivery.
Update your PIX or switch to firewall which is not b0rken.
-- Eero
