I saw this once before with my setup which sounds similar, ISA 2006 as NAT/Firewall/VPN, couple servers being published. We had the intermittent Internet access drops and then same deal, it would clear itself up after couple min or I would have to restart. Didn't always affect everyone, usually a random handful.
In my case it turned out to be my Internal NIC wasn't able to handle the load anymore. My ISA box is not on what you would call Server Hardware so it had a pretty standard desktop NIC handling everything, and it worked for years like that. But it was dropping packets and that was causing the intermittent Internet cut outs.
Verify your NIC is sever grade, if not try to get your hands on one. Also, it sounds like a NIC issue in general so maybe if it is good server grade hardware try updating NIC drivers, maybe try another known good NIC.