Loss of network connectivity.

[dinowuff]

Just a quick thought Are all the PC's affected at 100% patch level and non of the PC's affected at 70%.

Or vice-versa?

When did you put the deadline on all patches? Before this mess started or after?

[ByTeWrangler]

Affected machines also include completely patched machines.

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

I have checked ARP table of few machines but of these (about 8) only one had malicious entry pointing to another infected machine in the same VLAN. Other have only one entry pointing to local gateway (switch)

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

Nopes

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

Umm I didn’t see any of the switches do that except one that sent lot of ARP traffic then just stopped.

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

I am focusing on an intrusion because these branches are spread all across the country. Every branch has 2 switches ( overall 250+ branches and about 20 of them are having this issue). I really don’t think so many switches at the same time would start acting crazy, especially without ANY change being implemented.