Question : Big DNS problem, some internet servers reporting non-existent domain

Big DNS problem.  Multiple domains hosted with DNSpark.  Domains registered through 2014 and NetSol confirms no account issues.  When I query public DNS such as Verizon and Google all is fine (see below) but when I query some smaller IP's like XO.com I get a return of non-existent domain.  The problem I am having is that the government's (our client) DNS servers are showing non-existent domains.  This is happening on multiple domains all hosted at DNS park.  I have triple checked Network solutions and they have the correct DNS park name servers.  I can query DNS park servers and get  authoritative answers.   Trying to explain this level 1 support at any DNS provider I can find with the problem is trying to teach calculus to chickens...I am out of ideas other than moving DNS to another provider, however, the current system has worked for years and need to know why this is happening.  

>nslookup webmail.icrcsolutions.com 4.2.2.2
Server:  vnsc-bak.sys.gtei.net
Address:  4.2.2.2

Non-authoritative answer:
Name:    webmail.icrcsolutions.com
Address:  209.49.27.70


>nslookup webmail.icrcsolutions.com ns1.xo.com
Server:  ns1.xo.com
Address:  207.155.248.16

*** ns1.xo.com can't find webmail.icrcsolutions.com: Non-existent domain

C:\Users\cjwillis>nslookup
Default Server:  vse-hqs-dc32.vsehqs.com
Address:  10.1.10.6

> server 4.2.2.2
Default Server:  vnsc-bak.sys.gtei.net
Address:  4.2.2.2

> set q=n
unknown query type: n
> set q=ns
> icrcsolutions.com
Server:  vnsc-bak.sys.gtei.net
Address:  4.2.2.2

Non-authoritative answer:
icrcsolutions.com       nameserver = ns1.dnspark.net
icrcsolutions.com       nameserver = ns5.dnspark.net
icrcsolutions.com       nameserver = ns3.dnspark.net

Answer : Big DNS problem, some internet servers reporting non-existent domain

I shouldn't rely on ns1.xo.com, it doesn't return anything useful:

nslookup www.google.com ns1.xo.com

Which may be a restriction on that particular server to prevent public usage.

That doesn't make it any easier for you to troubleshoot though. I certainly can't see any problems with your name server configuration.

Chris