We were using a Non-AWS DNS resolver (aka Google) and we would often get dns resolution errors despite our NAT not being remotely taxed by the traffic.