I'm not sure what your setup is, but we were attempting to use a Barracuda Load Balancer which obviously won't work right. Looks like I'll be installing a ZCS proxy server.
You really can't load balance between mailbox servers at this time. ... at this time the only thing you can load balance this way is the proxy. The problem you're hitting is that you're only randomly hitting the right mailbox server. An account "lives" on only one mailbox server, and if your load balancer throws their connection to the wrong host, they're going to be constantly getting a redirect from that mailbox server telling it to go to the right place. The load balancer probably has no way of accomplishing this. You should bring up ZCS proxies and load balance connections to the proxies instead.