Can a DNS server return NXDOMAIN and an unresolved CNAME even though the alias exists

I think you may have a conceptual issue with how DNS works.

Only DNS servers performing recursive resolution cache lookups. The DNS servers that the affected users on "verizon DSL, comcast cable, verizon EVDO, site24x7 website" are using are the ones caching lookups.

The root DNS servers, .com servers, and the servers authoritative for your domain aren't caching lookups, because they're not providing recursive resolution service.

It's possible (likely, actually, from what I'm seeing in Google searches) that GoDaddy is sporadically returning NXDOMAINs for your domain, and those NXDOMAINs are being cached by recursive resolvers. (Per RFC2308, they should be cached, at most, either the TTL for the zone as specified in the SOA, or the SOA minimum-- whichever is least.)

Apparently, GoDaddy's "free" DNS service isn't too highly regarded. I don't use it, personally, so I can't comment on it.

There is no central "list" of DNS servers providing recursive resolution for you to "test against". (I have one here in my house, and I could spin a few more up on VMs if I needed to...) You need a reliable provider to be authoritative for your domain, and you just have to hope that everybody else in the world honors TTLs and acts as "good DNS citizens".

Edit:

"Recursive resolution" is the process by which the a DNS server resolves a record for which it is not authoritative. The process starts with the root DNS servers, and proceeds recursively (that is, a process that loops back on itself) through all the authoritative DNS servers for the domains specified in the query until the last DNS server is reached and the desired resource record (or a negative response) is returned.

For a three-level query, like "www.example.com", the following occurs (I am leaving out the fact that, all along the way, the ISP DNS server is checking its cache in lieu of issuing queries to remote DNS servers and putting the results it receives into its cache, to make this clearer and a bit more simplistic):

• Your PC issues a query to your specified DNS server (at your ISP, for example).

• The ISP DNS server verifies that it doesn't have a response in cache, and then queries one of the root DNS servers.

• The root DNS server, only being authoritative for the root, responds with a list of DNS servers authoritative for the gTLD specified in the query (.com, .net, .tv, .fu, etc). The protocol continues as such, w/ the full query always being sent to each successive DNS server throughout this process. Since it's not possible to know which DNS server will be authoritative for any given query and we want to minimize the number of round-trips, we always send the full domain in each query.

• The ISP DNS server queries one of the DNS servers returned as authoritative for the gTLD specified.

• The gTLD DNS server, being authoritative for the second-level domain (example, microsoft.com, example.com, etc) only, responds with a list of DNS servers authoritative for the second-level domain.

• The ISP DNS server queries one of the DNS servers returned as authoritative for the second-level domain.

• The DNS server authoritative for the second-level, being for the third-level domain (www.microsoft.com, ftp.example.com, etc), domain returns the record requested.

• The ISP DNS server returns the record your PC queried back to your PC.

Typically ISPs offer recursive resolution services to their Customers. The DNS servers at hosting providers that are authoritative for Customer hosted domains generally don't provide recursive service (and will return the root servers if queried for domains they aren't authoritative for).

It's not you. DNSstuff is reporting the same thing you are, in addition to a few other problems.