One of our netblocks appears to be filtered somewhere inside their network, preventing DNS lookups from completing, thus preventing e-mail from being delivered.
Am I reading this correctly? You are saying that you have engineered a single point of failure in your network and now you are suffering as a result? As the doctor said to the man who complained that his head hurt whenever he hit it with a hammer, don't do that! Every domain should ensure that it is "hosted" on name servers in several different netblocks which are in several different ASes, and preferably with some significant geographical diversity. There are many ways to do this ranging from renting colo for a server somewhere http://www.vix.com/personalcolo/ or working out a mutual arrangement with another ISP http://www.dnsist.net/ --Michael Dillon