I've seen the exact same symptoms before with another provider and it was a L3 Port-Channel that was not balanced properly due to a link being down which wasn't detected as such. It was also causing very sporadic latency spikes and dropped packets.
Jon