Recording the solution here, after trawling through innumerable forum posts, broken support links, etc.
Verizon FiOS supplies, by default, DNS recursors which spoof answers in place of NXDOMAIN, but ameliorate the impact by only doing so for queries in which the first label is "www". The page is a Yahoo/Teoma search. My, what a juicy target, should a government ever turn tyrannical -- force the revocation of domain registration for an unfavoured group, then serve Yahoo! with a warrant for query logs based on people accessing that domain.
Verizon's support pages don't document how to change this; an old NNsquad posting provided links to remaining support pages, but those which walked through the process split the articles over multiple pages, and none of the "Next" links worked. Highly amateurish.
OpenDNS forums noted that Verizon are intercepting queries not going to their own servers. So I haven't tried Google Public DNS (http://code.google.com/speed/public-dns/). That's my usual fallback plan.
Turns out that Verizon supply two sets of DNS recursor servers. Those where the IP address ends in a "12" octet are spoofers, those there the IP address ends in a "14" octet appear to be honest. While I haven't found official confirmation, it appears that the 12s are paired with 14s, so if you just change the last octet of the two addresses provided via DHCP, you're good to go.
One Airport restart later, and I'm currently clear. Right up until COICA coerces providers to implement interception of arbitrary (foreign) domains. Then I guess I'll be using IPsec to get to my colo box (which I never moved to the USA) and moving the Apple Airport to bridge mode, with something like my Soekris acting as Router again. I'd need to see about patches to Bind to support draft-vandergaast-edns-client-ip-01.txt though, to avoid hitting the wrong CDN endpoints.