Most IPSs think that DNS is an afterthought, to be stuffed in an old box and forgotten. Typical scenario: wait for a request, deny that request, then cache and honor the request the second time round.
Is that why sometimes I open a webpage and it gets stuck loading with the status bar displaying "Looking up example.com..."? If I reload the page it then loads immediately. I've been thinking that it has something to do with the cache, but why on earth would they deny the first request?