At this point (and I'm still not sure I understand the problem) I would say you are in a DoS situation and most likely it's a bad switch or router.

Check the ARP tables of an affected machine and then the arp table on the first switch it's attached to.

Do you have SNMP Traps set on all your routers and switches? Do any mac filtering?

I've seen switches just dump and rebuild the spanning tree for no apparent reason every few seconds never completely rebuilding.

Really I would focus (again if I understand your situation) on layer 2 and 3.

Hope this helps