DNS records resolve on some networks but not others after moving nameservers

Flush your own cache before testing too. On Windows it's ipconfig /flushdns, and restart the router if it does its own caching. A lot of "only broken on my network" turns out to be a stale record on that one machine.

Check DNSSEC before you blame propagation. If DNSSEC was on with the old DNS provider and the DS record is still sitting at your registrar, resolvers that validate (Google's 8.8.8.8 and Cloudflare's 1.1.1.1 both do) will fail the lookup, while a lot of ISP resolvers that don't validate will resolve it fine. That's exactly the some-networks-yes, some-no pattern. Either remove the old DS record or set up DNSSEC at the new provider and put their DS record in. If DNSSEC wasn't on, it's caching. Nameserver records often have a 24 to 48 hour TTL, so some resolvers still ask the old provider until it expires. Query a few resolvers directly with dig or nslookup to see which answer each one gives.