I'm trying to understand why one given DNS server is not resolving our domain correctly.

When I look up www.foo.com from this name server, a CNAME foo.bar.cc is correctly returned but there's no attached A record and the response status is NXDOMAIN. I understand that this could happen if the DNS server can not resolve the alias foo.bar.cc. However, if I use the same DNS server and look up foo.bar.cc directly, I always get the correct A record.

When using any other DNS servers I've tested (different ISPs, Google DNS, Open DNS) our domain resolves correctly.

Given this situation, is there some possible problem in our DNS that could cause this? Or does it seem like this given DNS server is to blame? The DNS server in question is used by a lot of people and it seems more likely that the problem is caused by us, but I don't see how - any clues?