Internet connection gets blocked every 5-10 minutes on our network...

Our company has its broadband connection via a cable modem (Cox Communications) running into a NETSCREEN5 router (managed by Cox Communications) that connects to our network thru 4 24-port 10/100 Ethernet switches and 3 48-port patch panels. For nearly 3 years we have had a few problems accessing the Internet until a few days ago. On Monday morning our company's broadband connection went down. I power cycled the cable modem and the router (per Cox communications instructions) and it was back up in less than a minute. Five minutes later it was down again. After a few repeats of this, I call Cox tech support line. They did their troubleshooting “thing” and the connection kept going down. I tried just power cycling the router and left the modem on and this accomplished the same thing. So, for the next several hours, while waiting for Cox to program a new router for us, I had to power cycle the router about every 5 to 10 minutes. Throughout the duration our internal network and intranet worked like a dream. We have NAT addresses on all our 70 or so PC's 7 of which are servers with public IP addresses that are translated through the Cox's router. I'd also like to mention that we also have virus scanners on our servers and on each PC as well as an excellent Spam filter on our mail server. Each PC also has spyware removal software
Cox eventually arrived and quickly swapped out the router. The gentleman left our building and a few hours later the problem started again. The came back the next morning and put in a 2nd replacement router. Before he left - the problem started again. The next day, the tech from Cox came back with his supervisor and they put one laptop (theirs) on the router and removed all connections to our network the connection stayed up for nearly an hour. They then plugged their router back into our network and within a few minutes it was down again.
This proved that the problem was not their equipment - it was something on our network. I am willing to accept this but what could be happening? If it is cutting off their router's ability to communicate through Ethernet, then what is happening to the router when this happens? I wanted them to tell me what was cutting off their router because I have no access privileges to it. They said they have no clue and said it’s our problem now. They suggested we painstakingly take each network connection individually down – wait to see what happens until the problem ceased.
I came in to work Thursday morning (yesterday) prepared to spend the day pulling each users PC's off the network and waiting to see what happened. To my surprise, the Internet stayed up all day long except for once. When I was told the connection was down I did not have time to reach the router to power cycle it before someone informed me that everything was ok again. That was it for yesterday. I assumed that perhaps Cox had actually had a problem and fixed it from their end and just did not want to admit fault.
Anyway, today has been a nightmare. Every five minutes the Internet goes down and I have to run to the router.
I checked to see if anyone was out the day before but no such luck. As far as I know there is nothing different from yesterday to today on out network. I have not been able to start taking individual users PCs down yet because I have other pressing things to finish. So I’ve power-cycled the router 5000 times today and still counting. I have tried port scanners and network bandwidth monitors and have found nothing. Our network is running perfectly (as far as I can see) and I'm going crazy. I know that there are many things that are out there, luring on the Internet that can cause problems like this but I don't know where to start.

Please help before I go insane!

Thanks in advance,
Michael