We have one ISA Server 2006 SP1 with 3 NIC (internal, external, DMZ). Randomly ISA server denies all new requests from NAT clients to Internet and DMZ. It lasts from few seconds to several hours and depends on the amout of traffic.
Winsock clients works but Exchange cannot send mails and VPNs doesn't connect. When ISA Server in this state the login to the console takes more than one minute.
It looks like DNS problem. On the internal NIC the internal DNS servers, on the external NIC the Internet provider's DSN servers are configured. ISA Server has access rule itself on DNS.