Response from AWS Support:

We have investigated this issue and are seeing incorrect responses from two of the .io nameservers: ns-a4.io and ns-a2.io.

These nameservers are returning NXDOMAIN intermittently for domains that do exist. As a result, once a resolver receives the erroneous response, it will cache the non-existence for the negative TTL, which for .io is set to 3600 seconds (1 hour).