Might be negative caching going on at the sender side. If they can't get a response, they set a TTL on the lack of a response - so future queries don't time out but instead immediately return NXDOMAIN. If you immediately tried after restarting your DNS service, it might still be assuming the server is down. Does it still do that after waiting? Like 12-24 hours?