Hows your 865L doing? 
So remember my DNS Relay issue? If I disable DNS relay and configure static DNS servers in the router's Internet Settings dialog (pointing to OpenDNS), while my PC's would get the correct set of DNS servers (the two OpenDNS ones and two from my ISP), all of their DNS lookups would timeout.
Well, since I had been running with DNS Relay ON as a workaround and I'd been having problems with OpenDNS sometimes not being used (going to welcome.opendns.com would claim I wasn't using OpenDNS despite the fact my static DNS servers in the router were pointing to OpenDNS), I was getting desperate for a real solution. So, I researched it a bit more last night and came across some information suggesting that turning off SPI (in Firewall Settings) would help. I just tried that and indeed it worked.
So, something about DNS Relay being off causes DNS conversations to be subjected to SPI and something in the router's SPI processing causes DNS queries to never complete. I saw a suggestion that the bug may have something to do with modern DNS queries requiring more than 512 bytes and speculation that the router fails to allocate more than that. I'm not expert in these matters by any means, so this explanation may not be 100% spot-on, but if I were a Dlink firmware engineer I'd use it as a clue as to where to start looking.
I regret that this morning I can't find the exact article that I found the SPI clue in. It was a well researched and very detailed account of a Dlink router's behavior in all the possible configuration states (relay on, relay off, SPI on, SPI off, etc.). I found it by searching Google for "DLINK DNS RELAY PROBLEM" and then just wading through the (many, many) hits. Apparently this issue goes back years and years and affects nearly every Dlink router, ever! On some routers there was no interaction with SPI (i.e. tunring off DNS relay was enough to fix it), but on others you also had to turn off SPI. Based on my results, it seems the 865L is one of those.
While I am happy to have found a way to get DNS working properly with this router, I am discouraged that this problem has been around so very long and that Dlink can't fix it once and for all. Further, I am not certain I want to run with SPI off for any length of time, so now I have to decide whether I want move on to some other router or not. I think I will run off to BestBuy today to pickup a competitor's router to test (and return if it doesn't pan out).
--
bc