Possible sources of 'no route to host'

Hey there,

Recently set up a new server. This server provides primary DNS. For the most part, everything is working fine. Networking is up, traffic is flowing, DNS is answering queries, etc.

One major issue I just discovered is a complete lack of network connectivity to one of Google's CIDRs

If I run a dig @8.8.8.8 mydomain.com (to test google's DNS resolution of any of my domains), it works 75% of the time, but 25% of the time it returns no results.

I've figured out that one specific Google owned CIDR (74.125.0.0/16) CAN connect to my server, but my server CANNOT connect to any IP in that CIDR. I have watched network traffic via tcpdump, and I see the DNS queries come in from 74.125.0.0/16, but no reply is sent.

The first thing I checked was both Iptables and hosts.deny, but these are not what is blocking the traffic. To test, I temporarily cleared the rules from both the firewall and hosts.deny and the 'no route to host' issue still exists.

I don't think this is a DNS service (or setup) issue because I cannot even ping or traceroute these 74.125.0.0/16 IPs. I can ping and traceroute these same Google IPs successfully from other servers on other networks though!

So my major question (plea for help) is, What am I missing?? What else could possibly prevent connectivity to this Google CIDR?

My last thoughts are maybe the hosting company has a firewall that is blocking, but considering this IP space is Google DNS, I doubt it.

For the life of me, I can't figure out what else might be preventing connectivity ...