The whole situation is a bizarre and I'm surprised any effect was noticed at all. You had to get unlucky enough that this ISP's recursive resolver cache expired in the 1-2 seconds you sent an NXDOMAIN. And then you have your NXDOMAIN TTL set far enough in the future it causes a problem. One possibility is the ISP ignores TTLs, setting its negative ones higher than the SOA settings and the others lower. I think the more likely scenario is weird caching-- either because of geopolitical boundaries or propagation issues on the service provider's side.
Before doing the switchover they might have lowered the TTL to something like 5s, which greatly increases the chance the TTL in the resolver cache would expire during the switchover. And then the ISP probably did set a longer than normal TTL on the record they inserted.
