At this point I think that the domain MAY be a red herring. Only one other domain is authenticating against it to send and they only have 3 users. They have however never complained to me about an issue. The other domains are either forced to send through their ISP.
Since this started last week it has resolved itself into a strange pattern of hit and miss. I upgraded to version 3.1.1 and for a time SASL authentication would work for a bit and then stop working and then start back up. After Then SASL authentication started working for some users and failing for others at the exact same time. For example today it started getting SASL authentication errors at 12:03PM Central Time) while at the exact same time users from the same locale (same IP even as they are PAT behind a firewall) were successfully authenticating.
I am convinced at this point that the problem is likely on their end somewhere. We tried to get them to start sending mail through their local ISP but the ISP only provides POP before SMTP. Not going to work in this case. The ISP is Telepacific.net, I have no idea if they are any good at all.
Sorry for placing the blame on Zimbra. I should have known better.