If their servers were unresponsive, then a long TTL might help as caching resolvers would retry and eventually get a successful result. Based on the output of the OPs tests, they are responding with incorrect NXDOMAIN results. This means that resolvers will cache the NXDOMAIN result using the SOA negative result TTL.

You could remove the delegation entries for the name servers that are returning results though, that might help.