Have you tried other virtual network cards, and/or PV network (netback for Xen or virtio for KVM)?
Under CentOS5/Xen, I was always using the default NIC, and I disctinctly remember I wasn't the only one in my team experiencing this problem. For CentOS6/kvm, I switched from the default to the e1000 at some point, but can't remember when. It was definitely working before and after I switched; so yes, this might have to do with the e1000.
That would help you isolate whether the problem was in the e1000 emulation (which I suspect is shared between KVM and Xen) or in the host network configuration (which, it sounds like, is non-trivial).
As this is a production system, I'd have to set up a clone and experiment with different options. I have an identical host machine, so no problem in that regard, but this will take some time I don't currently have.