maschimidt,
You should open a case ASAP to get to the bottom of your issue the quickest.
We can guess what is going on here, but it would take longer while your users suffer. TAC would be able to give you personalized service, and get to the bottom of things quicker.
There are users who might be able to chime in on anything they have experienced here, but TAC is probably the best route.