domain name system - Wildcard CNAME DNS records overriding specific A DNS records on one provider

Ran into a weird issue where a wildcard CNAME record (i.e. *.example.com) was overriding specific A records (i.e. host1.example.com, host2.example.com). It only affected Verizon Wireless's nameservers. The authoritative nameservers are controlled by Network Solutions (ns1.dnsbycomodo.net and ns2.dnsbycomodo.net).

Other providers' nameservers returned the correct results (OpenDNS and mxtoolbox.com), and it can't be a caching issue because the incorrect IPs (via the CNAME lookup) being returned were never previously used, and on top of that, the change was made 12 hours prior and the TTL on the records was only 7200.

Deleting the wildcard CNAME record appears to have solved the issue. Any thoughts on what happened? Has anyone else run into this? Is this just some bug with Verizon's DNS servers talking to Network Solutions'? Supposedly wildcard CNAME records have been valid for a while (Is a wildcard CNAME DNS record valid?).

EDIT:

Here's the order that things happened

Original config:
A *.example.com -> 1.1.1.1
A host1.example.com -> 2.2.2.2
A host2.example.com -> 3.3.3.3

Changed to:
Removed "A" *.example.com
Added CNAME *.example.com -> hostalias.example.net which resolves to 4.4.4.4

Outcome:
On Verizon queries to host1.example.com and host2.example.com started returning 4.4.4.4 whereas on OpenDNS and mxtoolbox.com, they still correctly returned 2.2.2.2 and 3.3.3.3, respectively.